Longest Palindromic Substring
Du erhältst eine Zeichenfolge s aus englischen Kleinbuchstaben. Gib ihre längste palindromische Teilzeichenfolge zurück: die längste Folge aufeinanderfolgender Buchstaben, die vorwärts und rückwärts gleich gelesen wird. Haben mehrere Teilzeichenfolgen dieselbe größte Länge, gib diejenige zurück, die am weitesten links beginnt.
Funktion
- sstring
- die Kleinbuchstaben-Zeichenfolge, nach der gesucht werden soll
- Gibt zurückstring
- die längste palindromische Teilzeichenfolge von s; bei mehreren gleich langen die am weitesten links stehende
Einschränkungen
1 ≤ s.length ≤ 2000senthält ausschließlich englische Kleinbuchstaben.- Wenn mehrere Palindrome die größte Länge haben, ist die Antwort dasjenige mit dem kleinsten Startindex.
Beispiele
- Eingabe
- s = "bananas"
- Ausgabe
- "anana"
- Erklärung
"anana"liest sich von beiden Seiten gleich und hat 5 Buchstaben. Kein längeres Stück funktioniert:"banana"beginnt mit b und endet mit a,"ananas"beginnt mit a und endet mit s, und das ganze Wort beginnt mit b und endet mit s.
- Eingabe
- s = "xyzzyabba"
- Ausgabe
- "yzzy"
- Erklärung
"yzzy"und"abba"sind beide Palindrome der Länge 4, und es gibt keine längeren."yzzy"beginnt bei Index 1, vor"abba"bei Index 5, und gewinnt daher den Gleichstand.
- Eingabe
- s = "abcd"
- Ausgabe
- "a"
- Erklärung
- Keine zwei Buchstaben sind gleich, daher besteht jedes Palindrom aus einem einzigen Buchstaben. Das am weitesten links stehende ist
"a".
Weiterführende Frage
Kannst du die Antwort in O(n)-Zeit finden?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Jedes Palindrom ist spiegelbildlich zu seiner Mitte. Sieh dir
"aba"und"abba"an: Wo liegt jeweils die Mitte, und wie viele mögliche Mitten hat eine Zeichenkette der Länge n?Beginne in der Mitte. Wenn die Buchstaben auf beiden Seiten übereinstimmen, hast du ein Palindrom, das zwei Buchstaben länger ist als zuvor. Wann musst du aufhören, es zu erweitern, und warum kann kein längeres Palindrom dieselbe Mitte haben?
Wachse für jede der
2n-1Mitten (jeden Buchstaben und jede Lücke zwischen zwei Nachbarn) nach außen, solange die Buchstaben übereinstimmen, und merke dir das längste Ergebnis. Ersetze das bisher beste Ergebnis nur, wenn ein neues Palindrom strikt länger ist, damit bei Gleichstand das linkeste gewinnt.
Lösung
Ein Palindrom ist um seine Mitte herum gespiegelt. Diese Mitte ist entweder ein einzelner Buchstabe (ungerade Länge, wie "anana") oder die Lücke zwischen zwei gleichen Buchstaben (gerade Länge, wie "abba"). Jedes Teilwort einzeln zu prüfen, ignoriert diese Struktur und kostet O(n³). Wenn man jedes Palindrom von seiner Mitte aus nach außen erweitert, wird jeder Vergleich wiederverwendet. Dadurch sinkt der Suchaufwand auf O(n²) Zeit bei O(1) zusätzlichem Speicher.
Jede Teilzeichenfolge überprüfen
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Ein Teilstring wird durch seinen ersten Index i und seinen letzten Index j festgelegt. Prüfe ihn mit zwei Zeigern: Vergleiche s[i] mit s[j], dann s[i+1] mit s[j-1] und so weiter, bis zum ersten Unterschied. Wenn sich die Zeiger treffen oder überkreuzen, ohne dass ein Unterschied auftritt, ist der Teilstring ein Palindrom. Behalte das längste gefundene Palindrom.
Für die Regel bei Gleichstand gehst du die Startpositionen von links nach rechts durch und ersetzt das bisher beste Ergebnis nur, wenn ein neues Palindrom strikt länger ist. Ein späteres Palindrom derselben Länge verdrängt dann nie ein früheres, sodass du das am weitesten links stehende zurückgibst.
Das betrachtet alle n(n+1)/2 Teilstrings, kann die Antwort also nicht übersehen. Es ist langsam, weil bei jedem Test bis zur Mitte des Teilstrings gegangen werden kann. Bei einer Zeichenkette aus 2000 Kopien von a ist jeder Teilstring ein Palindrom und jeder Test läuft bis zur Mitte: etwa n³/12 ≈ 6.7 × 10^8 Zeichenvergleiche.
Algorithmus
- Beginne mit dem ersten Buchstaben als bestem Ergebnis: Start 0, Länge 1.
- Vergleiche für jeden Start
iund jedes Endej ≥ idie Buchstaben von beiden Enden aus zur Mitte hin, bis sie sich unterscheiden oder die Zeiger aufeinandertreffen. - Wenn die Zeiger ohne Abweichung aufeinandertreffen, ist
s[i..j]ein Palindrom. - Wenn seine Länge
j-i+1die bisher beste übertrifft, speichereiund diese Länge. - Gib den Teilstring am besten Start mit der besten Länge zurück.
def longestPalindrome(s):
n = len(s)
best_start, best_len = 0, 1
for i in range(n):
for j in range(i, n):
# Compare s[i..j] from both ends toward the middle
left, right = i, j
while left < right and s[left] == s[right]:
left += 1
right -= 1
is_palindrome = left >= right
if is_palindrome and j - i + 1 > best_len:
best_start, best_len = i, j - i + 1
return s[best_start:best_start + best_len]Tabelle der Palindrome nach Länge
Idee
Die Brute-Force-Methode vergisst, was sie bereits gelernt hat. Wenn sie "anana" testet, vergleicht sie a mit a und dann n mit n. Der zweite Vergleich entspricht dem gesamten Test von "nan", den sie bereits durchgeführt hat. Die Regel, die Arbeit spart: s[i..j] ist ein Palindrom, wenn seine beiden Enden übereinstimmen und der Teil dazwischen, s[i+1..j-1], ein Palindrom ist. Ein Vergleich und ein gespeichertes Ergebnis reichen aus, um jedes Teilstück zu beurteilen.
Speichere die Ergebnisse in einer Tabelle pal[i][j] und fülle sie nach Länge. Jeder einzelne Buchstabe ist ein Palindrom. Ein Teilstück aus zwei Buchstaben ist genau dann ein Palindrom, wenn beide Buchstaben übereinstimmen. Bei größeren Längen verwendest du die Regel: Das innere Teilstück ist um zwei Buchstaben kürzer, daher ist sein Tabelleneintrag bereits ausgefüllt.
In "bananas" ist pal[1][5] ("anana") wahr, weil s[1] und s[5] beide a sind und pal[2][4] ("nan") wahr ist. Die Längen steigen an und die Startpositionen gehen von links nach rechts. Daher ist das erste Palindrom einer neuen Rekordlänge auch das am weitesten links liegende dieser Länge. Etwa n²/2 Tabelleneinträge kosten jeweils O(1), daher beträgt die Laufzeit O(n²); der Preis dafür ist der Speicherbedarf: 4 × 10^6 Einträge für n = 2000.
Algorithmus
- Erstelle eine Tabelle
palder Größe n × n, die vollständig auf false gesetzt ist. - Gehe jede Länge von 1 bis n und jeden Startwert
idurch, bei dem das Endej = i+length-1innerhalb des Strings liegt, und überprüfe die beiden Endbuchstaben. - Markiere
pal[i][j], wenn sie übereinstimmen und die Länge höchstens 2 beträgt oderpal[i+1][j-1]true ist. - Wenn die Länge einer markierten Zelle die bisher beste übertrifft, speichere
iund die Länge. - Gib den Teilstring ab dem besten Start zurück.
def longestPalindrome(s):
n = len(s)
# pal[i][j] is True when s[i..j] reads the same both ways
pal = [[False] * n for _ in range(n)]
best_start, best_len = 0, 1
for length in range(1, n + 1):
for i in range(n - length + 1):
j = i + length - 1
# Equal ends, and the part inside them is a palindrome (or too short to matter)
if s[i] == s[j] and (length <= 2 or pal[i + 1][j - 1]):
pal[i][j] = True
if length > best_len:
best_start, best_len = i, length
return s[best_start:best_start + best_len]Um jeden Mittelpunkt erweitern
Idee
Jedes Palindrom hat eine Mitte. Ein Palindrom mit ungerader Länge wie "anana" hat einen Buchstaben als Mitte; ein Palindrom mit gerader Länge wie "abba" hat die Lücke zwischen seinen beiden mittleren Buchstaben als Mitte. Eine Zeichenkette der Länge n hat n Buchstaben und n-1 Lücken, also 2n-1 mögliche Mittelpunkte.
Gehe von einem Mittelpunkt aus nach außen, auf jeder Seite jeweils einen Buchstaben, solange die beiden Buchstaben übereinstimmen. Jeder Schritt bestätigt ein Palindrom, das zwei Buchstaben länger ist. Die erste Abweichung oder das Ende der Zeichenkette beendet den Durchlauf, und kein längeres Palindrom kann denselben Mittelpunkt haben, da es das abweichende Buchstabenpaar enthalten würde. Ein Durchlauf nach außen findet also für jeden Mittelpunkt das längste Palindrom, und das längste davon ist die gesuchte Antwort.
Beginne in "bananas" beim Buchstaben a an Index 3. Die Buchstaben an den Indizes 2 und 4 sind beide n, die Buchstaben an den Indizes 1 und 5 sind beide a, und die Buchstaben an den Indizes 0 und 6 sind b und s, also endet der Durchlauf bei einer Länge von 5. Der Anfang ist 3 - (5-1)/2 = 1, was "anana" ergibt. Dieselbe Formel, center - (length-1)/2 abgerundet, funktioniert auch für die Mittelpunkte zwischen den Buchstaben.
Gehe die Mittelpunkte von links nach rechts durch und ersetze das bisher beste Ergebnis nur bei einer strikt größeren Länge. Zwei Palindrome gleicher Länge haben dieselbe Parität, und das mit dem früheren Mittelpunkt beginnt weiter links, also gewinnt das am weitesten links liegende. Der ungünstigste Fall ist eine Zeichenkette aus lauter gleichen Buchstaben: Jeder Mittelpunkt läuft bis zum näheren Rand, also etwa n²/2 = 2 × 10^6 Schritte für n = 2000, und der Speicherbedarf beträgt nur wenige Ganzzahlen.
Algorithmus
- Schreibe
expand(left, right): Solange sich beide Indizes innerhalb der Zeichenkette befinden und die Buchstaben übereinstimmen, bewegeleftnach unten undrightnach oben. Gibright-left-1zurück. - Nimm für jede Mitte von 0 bis n-1 den größeren Wert von
expand(center, center)undexpand(center, center+1). - Wenn diese Länge die bisher beste übertrifft, setze den besten Start auf
center - (length-1)/2, abgerundet, und die beste Länge auf diesen Wert. - Gib den Teilstring am besten Start mit der besten Länge zurück.
def expand(s, left, right):
# Grow outward while the two ends match; return the palindrome's length
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
def longestPalindrome(s):
best_start, best_len = 0, 1
for center in range(len(s)):
# Odd lengths grow from one letter, even lengths from the gap after it
length = max(expand(s, center, center), expand(s, center, center + 1))
if length > best_len:
best_start = center - (length - 1) // 2
best_len = length
return s[best_start:best_start + best_len]
Stolperfallen und Grenzfälle
Die Idee ist kurz, deshalb verstecken sich die Fehler in den Details: den geraden Mittelpunkten, der Länge nach dem Durchlauf, der Regel für Gleichstände und dem Slicing.
- Wer nur um Buchstaben herum erweitert, übersieht alle geraden Palindrome. Bei
"abba"wird so"a"statt"abba"zurückgegeben. - Der Durchlauf stoppt jeweils einen Schritt hinter jedem Ende, daher lautet das Palindrom
s[left+1..right-1]mit der Längeright-left-1. Mitright-left+1kommen zwei Buchstaben hinzu, die nicht übereinstimmen. - Wird das beste Ergebnis bei gleicher Länge ersetzt, erhält man das am weitesten rechts stehende Palindrom: Bei
"xyzzyabba"erhält man"abba"statt"yzzy". - Bei einem Mittelpunkt zwischen zwei Buchstaben liegt
center - length/2eine Position zu weit links. In"xyzzyabba"hat die Lücke nach Index 2 die Länge 4, und der Start ist2 - (4-1)/2 = 1, nicht 0. - Die Slicing-APIs unterscheiden sich: C++
substrund C#Substringerwarten eine Länge, während JavaScriptsubstringund Javasubstringeinen Endindex erwarten. - In der Tabelle liest das Befüllen der Zeilen nach Startindex von 0 aufwärts
pal[i+1][j-1], bevor dieser Wert berechnet wurde. Fülle nach Länge auf oder durchlaufe die Startindizes rückwärts.
Häufige Fragen3
Wie hoch ist die Zeitkomplexität des längsten palindromischen Teilstrings?
Die Expansion um Mittelpunkte benötigt O(n²) Zeit und O(1) zusätzlichen Speicher. Der Tabellenansatz benötigt ebenfalls O(n²) Zeit, aber O(n²) Speicher, und das Überprüfen jedes Teilstrings benötigt O(n³). Der Algorithmus von Manacher erreicht O(n), wird aber bei Vorstellungsgesprächen selten erwartet.
Warum verwendet „expand around center“ 2n-1 Mittelpunkte?
Ein Palindrom mit ungerader Länge hat einen mittleren Buchstaben, und eines mit gerader Länge hat eine mittlere Lücke zwischen zwei gleichen Buchstaben. Eine Zeichenkette aus n Buchstaben hat n Buchstaben und n-1 Lücken zwischen benachbarten Buchstaben. Wenn man nur von den Buchstaben ausgehend erweitert, übersieht man Palindrome wie "abba".
Was ist Manachers Algorithmus?
Es findet in insgesamt O(n) Zeit das längste Palindrom um jedes Zentrum. Es behält das Palindrom bei, das bisher am weitesten nach rechts reicht, und ein Zentrum innerhalb dieses Palindroms beginnt mit der Antwort seines Spiegelzentrums, sodass kein Buchstabe erneut von Grund auf verglichen wird. Es lohnt sich, den Namen zu kennen; „expand around center“ ist die Lösung, die Interviewer normalerweise erwarten.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def longestPalindrome(s):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argument
s = "bananas"
Erwartete Ausgabe
"anana"