Longest Palindromic Substring

ŚrednieDwa wskaźniki Programowanie dynamiczne

+10

Otrzymujesz ciąg s złożony z małych liter alfabetu angielskiego. Zwróć jego najdłuższy podciąg palindromiczny: najdłuższy ciąg kolejnych liter, który czyta się tak samo od początku do końca i od końca do początku. Jeśli kilka podciągów ma taką samą maksymalną długość, zwróć ten, który zaczyna się najbardziej z lewej strony.

Funkcja

longestPalindrome(s: string) → string

sstring: ciąg znaków zapisany małymi literami, którego należy szukać
Zwracastring: najdłuższy podciąg palindromiczny w s, najbardziej z lewej strony, gdy kilka ma taką samą długość

Ograniczenia

1 ≤ s.length ≤ 2000
s zawiera wyłącznie małe litery alfabetu angielskiego.
Gdy kilka palindromów ma największą długość, odpowiedzią jest ten o najmniejszym indeksie początkowym.

Przykłady

Wejście: s = "bananas"
Wyjście: "anana"
Wyjaśnienie: "anana" czyta się tak samo z obu stron i ma 5 liter. Żaden dłuższy fragment nie działa: "banana" zaczyna się na b i kończy na a, "ananas" zaczyna się na a i kończy na s, a całe słowo zaczyna się na b i kończy na s.

Wejście: s = "xyzzyabba"
Wyjście: "yzzy"
Wyjaśnienie: "yzzy" i "abba" to palindromy o długości 4 i nie istnieje nic dłuższego. "yzzy" zaczyna się na indeksie 1, przed "abba" na indeksie 5, więc wygrywa w przypadku remisu.

Wejście: s = "abcd"
Wyjście: "a"
Wyjaśnienie: Żadne dwie litery nie są takie same, więc każdy palindrom składa się z jednej litery. Najbardziej na lewo położona litera to "a".

+18 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy potrafisz znaleźć odpowiedź w czasie O(n)?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Palindrom odbija się symetrycznie względem środka, którym jest albo jedna litera (nieparzysta długość, jak "anana"), albo odstęp między dwiema takimi samymi literami (parzysta długość, jak "abba"). Sprawdzanie każdego podciągu osobno pomija tę strukturę i wymaga O(n³) operacji. Rozszerzanie każdego palindromu na zewnątrz od jego środka pozwala ponownie wykorzystać każde porównanie, co skraca wyszukiwanie do O(n²) czasu przy O(1) dodatkowej pamięci.

Sprawdź każdy podciąg

Poprawne, ale nie kończy się na największych testach

Intuicja

Podciąg jest wyznaczony przez swój pierwszy indeks i i ostatni indeks j. Sprawdź go za pomocą dwóch wskaźników: porównaj s[i] z s[j], następnie s[i+1] z s[j-1] i tak dalej, zatrzymując się przy pierwszej niezgodności. Jeśli wskaźniki się spotkają lub miną, nie napotykając niezgodności, podciąg jest palindromem. Zachowaj najdłuższy znaleziony.

Aby rozstrzygnąć remis, przechodź po indeksach początkowych od lewej do prawej i zastępuj najlepszy wynik tylko wtedy, gdy nowy palindrom jest ściśle dłuższy. Późniejszy palindrom o tej samej długości nie zastąpi więc wcześniejszego, dlatego zwrócisz ten najbardziej z lewej.

Ta metoda sprawdza wszystkie n(n+1)/2 podciągów, więc nie może pominąć odpowiedzi. Jest powolna, ponieważ każde sprawdzenie może przejść przez połowę podciągu. Dla ciągu składającego się z 2000 kopii a każdy podciąg jest palindromem, a każde sprawdzenie dochodzi do środka: około n³/12 ≈ 6.7 × 10^8 porównań liter.

Algorytm

Zacznij od najlepszej odpowiedzi: początek 0, długość 1.
Dla każdego początku i i każdego końca j ≥ i porównuj litery od obu końców w kierunku środka, aż się różnią lub wskaźniki się spotkają.
Jeśli wskaźniki się spotkały i nie było różnicy, s[i..j] jest palindromem.
Jeśli jego długość j-i+1 jest większa od najlepszej, zapisz i i tę długość.
Zwróć podciąg zaczynający się od najlepszego początku i mający najlepszą długość.

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]

Tabela palindromów według długości

Intuicja

Algorytm brute force zapomina to, czego się nauczył. Gdy sprawdza "anana", porównuje a z a, a potem n z n; drugie porównanie jest całym testem "nan", który już wykonał. Reguła, która oszczędza pracę: s[i..j] jest palindromem, gdy jego dwa końce są takie same, a część między nimi, s[i+1..j-1], jest palindromem. Jedno porównanie i jedna zapisana odpowiedź wystarczą, by rozstrzygnąć kwestię każdego podciągu.

Zapisuj odpowiedzi w tablicy pal[i][j] i wypełniaj ją według długości. Każda pojedyncza litera jest palindromem. Podciąg złożony z dwóch liter jest palindromem, gdy obie litery są takie same. Dla większych długości zastosuj regułę: wnętrze jest krótsze o dwie litery, więc jego komórka jest już wypełniona.

W ciągu "bananas" pal[1][5] ("anana") ma wartość true, ponieważ s[1] i s[5] to obie litery a, a pal[2][4] ("nan") ma wartość true. Długości rosną, a początki przesuwają się od lewej do prawej, więc pierwszy palindrom o nowej rekordowej długości jest również najbardziej wysuniętym w lewo palindromem o tej długości. Około n²/2 komórek, z których każda wymaga O(1) czasu, oznacza złożoność czasową O(n²); ceną jest pamięć — 4 × 10^6 komórek dla n = 2000.

Algorytm

Utwórz tabelę n × n pal, wypełnioną wartościami false.
Dla każdej długości od 1 do n i każdego początku i, dla którego koniec j = i+length-1 mieści się w ciągu, sprawdź obie skrajne litery.
Oznacz pal[i][j], gdy litery są takie same, a długość wynosi najwyżej 2 lub pal[i+1][j-1] ma wartość true.
Gdy długość oznaczonej komórki jest większa niż dotychczasowa najlepsza, zapisz i i tę długość.
Zwróć podciąg zaczynający się w najlepszym miejscu.

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]

Rozwiń wokół każdego środka

Intuicja

Każdy palindrom ma środek. W przypadku palindromu o nieparzystej długości, takiego jak "anana", środkiem jest litera; palindrom o parzystej długości, taki jak "abba", ma środek w przerwie między dwiema środkowymi literami. Łańcuch o długości n ma n liter i n-1 przerw, czyli 2n-1 możliwych środków.

Od środka przesuwaj się na zewnątrz, po jednej literze z każdej strony, dopóki obie litery są takie same. Każdy krok potwierdza istnienie palindromu dłuższego o dwie litery. Pierwsza niezgodność albo krawędź łańcucha kończy przejście, a żaden dłuższy palindrom nie może mieć tego samego środka, ponieważ zawierałby niezgodną parę. Jedno przejście na zewnątrz pozwala więc znaleźć najdłuższy palindrom wokół każdego środka, a odpowiedzią jest najdłuższy z nich.

W "bananas" zacznij od litery a o indeksie 3. Litery na pozycjach 2 i 4 to n, litery na pozycjach 1 i 5 to a, a litery na pozycjach 0 i 6 to b i s, więc przejście kończy się na długości 5. Początek to 3 - (5-1)/2 = 1, co daje "anana". Ten sam wzór, center - (length-1)/2 zaokrąglony w dół, działa również dla środków znajdujących się w przerwach.

Przechodź przez środki od lewej do prawej i zastępuj najlepszy wynik tylko wtedy, gdy długość jest ściśle większa. Dwa palindromy o tej samej długości mają tę samą parzystość, a ten o wcześniejszym środku zaczyna się wcześniej, więc wygrywa ten najbardziej z lewej. Najgorszy przypadek to łańcuch składający się z powtarzającej się litery: dla każdego środka przejście sięga do bliższej krawędzi, co daje około n²/2 = 2 × 10^6 kroków dla n = 2000, a pamięć zajmuje kilka liczb całkowitych.

Algorytm

Napisz expand(left, right): dopóki oba indeksy znajdują się wewnątrz ciągu i litery są takie same, zmniejszaj left i zwiększaj right. Zwróć right-left-1.
Dla każdego środka od 0 do n-1 wybierz większą wartość spośród expand(center, center) i expand(center, center+1).
Jeśli ta długość jest większa od dotychczas najlepszego wyniku, ustaw najlepszy początek na center - (length-1)/2, zaokrąglony w dół, a najlepszą długość na tę wartość.
Zwróć podciąg zaczynający się od najlepszego początku i mający najlepszą długość.

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]

Pułapki i przypadki brzegowe

Pomysł jest prosty, więc błędy kryją się w szczegółach: parzyste środki, długość po przejściu, zasada rozstrzygania remisu i wycinanie fragmentów.

Rozszerzanie tylko wokół liter pomija wszystkie palindromy parzystej długości. Dla "abba" zwraca "a" zamiast "abba".
Przejście zatrzymuje się o jeden krok za każdym końcem, więc palindrom to s[left+1..right-1], a jego długość wynosi right-left-1. Użycie right-left+1 dodaje dwie niedopasowane litery.
Zastąpienie najlepszego wyniku przy równej długości zwraca palindrom najbardziej po prawej stronie: dla "xyzzyabba" będzie to "abba" zamiast "yzzy".
Dla środka w przerwie center - length/2 daje wynik przesunięty o jeden za daleko w lewo. W "xyzzyabba" przerwa za indeksem 2 ma długość 4, a początek to 2 - (4-1)/2 = 1, a nie 0.
Interfejsy do wycinania fragmentów różnią się: C++ substr i C# Substring przyjmują długość, natomiast JavaScript substring i Java substring przyjmują indeks końcowy.
W tabeli wypełnianie wierszy według początku, od 0 wzwyż, powoduje odczyt pal[i+1][j-1] przed jego wypełnieniem. Wypełniaj tabelę według długości albo przechodź przez początki od końca.

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu najdłuższego palindromicznego podciągu?

Rozszerzanie wokół środków zajmuje O(n²) czasu i O(1) dodatkowej pamięci. Podejście z tabelą również zajmuje O(n²) czasu, ale wymaga O(n²) pamięci, a sprawdzanie każdego podciągu zajmuje O(n³). Algorytm Manachera osiąga O(n), ale rozmówcy kwalifikacyjni rzadko tego oczekują.

Dlaczego rozwijanie wokół środka wykorzystuje 2n-1 środków?

Palindrom o nieparzystej długości ma środkową literę, a palindrom o parzystej długości ma środkową przerwę między dwiema takimi samymi literami. Ciąg znaków o długości n ma n liter i n-1 przerw między sąsiednimi literami. Rozszerzanie tylko od liter pomija palindromy takie jak "abba".

Czym jest algorytm Manachera?

Znajduje najdłuższy palindrom wokół każdego środka w łącznym czasie O(n). Zachowuje palindrom, który jak dotąd sięga najdalej w prawo, a środek znajdujący się w jego obrębie zaczyna od odpowiedzi dla swojego lustrzanego środka, dzięki czemu żadna litera nie jest ponownie porównywana od początku. Warto znać tę metodę z nazwy; rozszerzanie wokół środka to rozwiązanie, którego zwykle oczekują osoby prowadzące rozmowy kwalifikacyjne.

Czym najdłuższy palindromiczny podciąg różni się od najdłuższej palindromicznej podsekwencji?

Podciąg znaków to ciąg kolejnych liter, podczas gdy podciąg może pomijać litery. W "character" najdłuższy palindromiczny podciąg znaków to "ara", ale "carac" jest palindromicznym podciągiem o długości 5. Wersję dotyczącą podciągu rozwiązuje się za pomocą tabeli dla (i, j), pomijając jeden z końców, gdy oba końce są różne.

Python

def longestPalindrome(s):
    # Napisz tutaj kod

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

s = "bananas"

Oczekiwane

"anana"

Longest Palindromic Substring

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Sprawdź każdy podciąg

Tabela palindromów według długości

Rozwiń wokół każdego środka

Pułapki i przypadki brzegowe

Najczęstsze pytania4

Podobne zadania