Überprüft, ob die Teilzeichenfolgen von drei angegebenen Zeichenfolgen zu einer Palindromzeichenfolge verkettet werden können

Palindrome sind ein faszinierendes Thema in der Informatik und Programmierung. Ein Palindrom ist eine Folge von Wörtern, Phrasen, Zahlen oder anderen Zeichen, die von vorne nach hinten genauso gelesen wird wie von hinten nach vorne, wobei Leerzeichen, Satzzeichen und Groß-/Kleinschreibung ignoriert werden. In diesem Artikel untersuchen wir ein einzigartiges Problem: Wie lässt sich feststellen, ob Teilzeichenfolgen aus drei gegebenen Zeichenketten zu einem Palindrom verkettet werden können? Diese Frage kommt häufig in Vorstellungsgesprächen vor und kann mit verschiedenen Techniken gelöst werden, darunter String-Operationen, Hashing und dynamische Programmierung.

Problemstellung

Bei drei Strings besteht die Aufgabe darin, zu prüfen, ob es möglich ist, aus jedem gegebenen String Teilstrings auszuwählen und diese zu einem Palindrom zu verketten.

Methode

Der allgemeine Ansatz zur Lösung dieses Problems umfasst die folgenden Schritte -

• Verketten Sie drei Zeichenfolgen auf sechs verschiedene Arten (alle Permutationen von drei Zeichenfolgen).

• Überprüfen Sie für jede verkettete Zeichenfolge, ob sie ein Palindrom bilden kann.

Um zu prüfen, ob eine Zeichenfolge ein Palindrom bilden kann, müssen wir sicherstellen, dass nicht mehr als ein Zeichen mit ungerader Häufigkeit in der Zeichenfolge vorkommt.

C++-Lösung

Beispiel

Dies ist die C++-Funktion, die die obige Methode implementiert −

#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;
}

Ausgabe

No

Beispielhafte Testfallbeschreibung

Lassen Sie uns die Zeichenfolgen „abc“, „def“ und „cba“ erstellen.

Die Funktion canFormPalindrome(str) prüft, ob die gesamte Zeichenfolge in ein Palindrom umgeordnet werden kann, anstatt zu prüfen, ob es sich bereits um ein Palindrom handelt.

Wenn Sie die Zeichenfolgen „abc“, „de“ und „edcba“ verwenden und diese verketten, entsteht die Zeichenfolge „abcdeedcba“, die nicht in ein Palindrom umgeordnet werden kann, da sie zwei „d“-Zeichen und zwei „e“-Zeichen enthält, sondern nur eines 'b'-Zeichen. Daher ist die Ausgabe tatsächlich „Nein“.

Die Funktion checkSubstrings prüft alle möglichen Verkettungen von drei Strings. Allerdings kann keines davon zu einem Palindrom neu angeordnet werden, daher lautet die Ausgabe „Nein“.

Fazit

Die Fähigkeit, solche Fragen zu lösen, trägt nicht nur dazu bei, Interviews gut zu programmieren, sondern verbessert auch die Fähigkeiten zur Problemlösung, die für jeden Softwareentwickler unerlässlich sind. Diese Frage ist ein gutes Beispiel dafür, wie String-Manipulation und Hashing zur Lösung komplexer Probleme eingesetzt werden können. Übung und Verständnis sind der Schlüssel zur Beherrschung dieser Themen.

Das obige ist der detaillierte Inhalt vonÜberprüft, ob die Teilzeichenfolgen von drei angegebenen Zeichenfolgen zu einer Palindromzeichenfolge verkettet werden können. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!