Vérifie si les sous-chaînes de trois chaînes données peuvent être concaténées en une chaîne palindrome

Les palindromes sont un sujet fascinant en informatique et en programmation. Un palindrome est une séquence de mots, d'expressions, de chiffres ou d'autres caractères qui se lit de la même manière d'avant en arrière et d'arrière en avant, en ignorant les espaces, la ponctuation et la casse. Dans cet article, nous examinerons un problème unique : comment déterminer si les sous-chaînes de trois chaînes données peuvent être concaténées pour former un palindrome. Cette question est une question d'entretien courante et peut être résolue à l'aide de diverses techniques, notamment la manipulation de chaînes, le hachage et la programmation dynamique.

Énoncé du problème

Étant donné trois chaînes, la tâche consiste à vérifier s'il est possible de sélectionner des sous-chaînes de chaque chaîne donnée et de les concaténer pour former un palindrome.

Méthode

L'approche générale pour résoudre ce problème implique les étapes suivantes -

• Concaténez trois chaînes de six manières différentes (toutes les permutations de trois chaînes).

• Pour chaque chaîne concaténée, vérifiez si elle peut former un palindrome.

Pour vérifier si une chaîne peut former un palindrome, nous devons nous assurer que pas plus d'un caractère n'apparaît avec une fréquence impaire dans la chaîne.

Solution C++

Exemple

C'est la fonction C++ qui implémente la méthode ci-dessus −

#include<bits/stdc++.h>
using namespace std;

bool canFormPalindrome(string str) {
   vector<int> count(256, 0);
   for (int i = 0; str[i]; i++)
      count[str[i]]++;
   int odd = 0;
   for (int i = 0; i < 256; i++) {
      if (count[i] & 1)
         odd++;
      if (odd > 1)
         return false;
   }
   return true;
}

bool checkSubstrings(string s1, string s2, string s3) {
   string arr[] = {s1, s2, s3, s1, s3, s2};
   for (int i = 0; i < 3; i++) {
      if (canFormPalindrome(arr[i] + arr[i + 1] + arr[i + 2]))
         return true;
   }
   return false;
}

int main() {
   string s1 = "abc";
   string s2 = "def";
   string s3 = "cba";
   if (checkSubstrings(s1, s2, s3))
      cout << "Yes\n";
   else
      cout << "No\n";
   return 0;
}

Sortie

No

Exemple de description de cas de test

Créons les chaînes "abc", "def" et "cba".

La fonction canFormPalindrome(str) vérifie si la chaîne entière peut être réorganisée en palindrome, au lieu de vérifier si c'est déjà un palindrome.

En utilisant les chaînes "abc", "de" et "edcba", la chaîne "abcdeedcba" obtenue en les concaténant ne peut pas être réarrangée en palindrome car elle comporte deux caractères 'd' et deux caractères 'e', ​​mais un seul ' b'caractère. Par conséquent, la sortie est bien « Non ».

La fonction checkSubstrings vérifie toutes les concaténations possibles de trois chaînes. Cependant, aucun de ces éléments ne peut être réorganisé pour former un palindrome, le résultat est donc « Non ».

Conclusion

Être capable de résoudre de telles questions aide non seulement à réussir les entretiens de codage, mais améliore également les compétences en résolution de problèmes qui sont essentielles pour tout ingénieur logiciel. Cette question est un bon exemple de la façon d'utiliser la manipulation et le hachage de chaînes pour résoudre des problèmes complexes. La pratique et la compréhension sont les clés pour maîtriser ces sujets.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!