Longest Palindromic Substring

+10

Küçük harfli İngilizce harflerden oluşan bir s dizgesi verilir. En uzun palindromik alt dizgesini döndürün: baştan ve sondan okunduğunda aynı olan ardışık harflerin en uzun dizisini. Birden fazla alt dizge aynı en uzun uzunluğa sahipse, en soldan başlayanı döndürün.

Fonksiyon

longestPalindrome(s: string) → string

sstring: aranacak küçük harfli dize
Döndürürstring: s içindeki en uzun palindromik alt dize; birden fazla alt dize eşit uzunluktaysa en soldaki

Kısıtlar

1 ≤ s.length ≤ 2000
s yalnızca küçük İngilizce harfleri içerir.
Birden fazla palindrom en uzun uzunluğa sahipse, yanıt başlangıç indeksi en küçük olanıdır.

Örnekler

Girdi: s = "bananas"
Çıktı: "anana"
Açıklama: "anana" her iki yönden de aynı şekilde okunur ve 5 harften oluşur. Daha uzun hiçbir parça işe yaramaz: "banana" b ile başlar ve a ile biter, "ananas" a ile başlar ve s ile biter, tüm sözcük ise b ile başlar ve s ile biter.

Girdi: s = "xyzzyabba"
Çıktı: "yzzy"
Açıklama: "yzzy" ve "abba" ikisi de uzunluğu 4 olan palindromlardır ve daha uzun hiçbir şey yoktur. "yzzy", "abba" indeks 5'te başlamadan önce indeks 1'de başlar; bu yüzden eşitliği kazanır.

Girdi: s = "abcd"
Çıktı: "a"
Açıklama: Hiçbir iki harf eşit değildir, bu yüzden her palindrom tek bir harften oluşur. En soldaki harf "a"’dır.

Gönderirken +18 gizli test

Ek soru

Yanıtı O(n) zamanda bulabilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Bir palindrom, ortasına göre simetriktir ve bu orta nokta ya bir harftir (uzunluğu tek olan "anana" gibi) ya da birbirine eşit iki harfin arasındaki boşluktur (uzunluğu çift olan "abba" gibi). Her alt diziyi ayrı ayrı kontrol etmek bu yapıyı göz ardı eder ve O(n³) maliyetine yol açar. Her palindromu ortasından başlayarak dışa doğru genişletmek, tüm karşılaştırmaları yeniden kullanır; böylece arama O(n²) zamana ve O(1) ek belleğe iner.

Her alt dizgeyi kontrol et

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Bir alt dize, ilk indeksi i ve son indeksi j ile belirlenir. İki işaretçiyle test et: s[i] ile s[j] değerlerini karşılaştır, sonra s[i+1] ile s[j-1] değerlerini karşılaştır ve ilk uyuşmazlıkta dur. İşaretçilerden biriyle karşılaşmadan veya kesişmeden buluşursa, alt dize bir palindromdur. Bulduğun en uzununu sakla.

Eşitlik kuralı için başlangıçları soldan sağa doğru dolaş ve en iyiyi yalnızca yeni bir palindrom kesinlikle daha uzunsa değiştir. Böylece aynı uzunluktaki daha sonraki bir palindrom daha önce bulunanı asla geçemez ve en soldakini döndürürsün.

Bu yöntem tüm n(n+1)/2 alt dizelere bakar, dolayısıyla yanıtı kaçırmaz. Yavaştır, çünkü her test alt dizenin yarısı boyunca ilerleyebilir. a harfinden 2000 adet içeren bir dizgede her alt dize bir palindromdur ve her test ortasına kadar ilerler: yaklaşık n³/12 ≈ 6.7 × 10^8 harf karşılaştırması.

Algoritma

Başlangıç olarak ilk harfi en iyi kabul et: başlangıç 0, uzunluk 1.
Her i başlangıcı ve her j ≥ i bitişi için, harfler farklı olana veya işaretçiler buluşana kadar iki uçtan ortaya doğru harfleri karşılaştır.
İşaretçiler uyuşmazlık olmadan buluştuysa s[i..j] bir palindromdur.
Uzunluğu j-i+1 en iyiyi geçiyorsa i değerini ve bu uzunluğu kaydet.
En iyi başlangıçtan, en iyi uzunluktaki alt diziyi döndür.

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]

Uzunluğa göre palindromlar tablosu

Sezgi

Kaba kuvvet, öğrendiklerini unutur. "anana" dizgesini test ederken a ile a'yı karşılaştırır, ardından n ile n'yi karşılaştırır; ikinci karşılaştırma, daha önce çalıştırdığı "nan" testinin tamamıdır. İş yükünü azaltan kural şudur: iki ucu eşleşiyorsa ve aralarındaki bölüm s[i+1..j-1] bir palindromsa, s[i..j] de bir palindromdur. Her alt dizge için tek bir karşılaştırma ve kaydedilmiş tek bir yanıt yeterlidir.

Yanıtları pal[i][j] tablosunda sakla ve uzunluğa göre doldur. Her tek harf bir palindromdur. İki harfli bir alt dizge, iki harf de eşleşiyorsa palindromdur. Daha uzun dizgeler için kuralı kullan: iç bölümün uzunluğu iki harf daha kısadır, dolayısıyla hücresi zaten doldurulmuştur.

"bananas" dizgesinde pal[1][5] ("anana") doğrudur; çünkü s[1] ve s[5] ikisi de a'dır ve pal[2][4] ("nan") doğrudur. Uzunluklar artar ve başlangıç konumları soldan sağa ilerler; bu nedenle yeni bir rekor uzunluğa ulaşan ilk palindrom, aynı zamanda o uzunluktaki en soldaki palindromdur. Yaklaşık n²/2 hücrenin her biri O(1) maliyetlidir, bu yüzden zaman karmaşıklığı O(n²)'dir; bedeli ise bellektir: n = 2000 için 4 × 10^6 hücre.

Algoritma

Tüm değerleri false olan n × n boyutunda bir pal tablosu oluştur.
1'den n'ye kadar her uzunluk ve bitiş konumu j = i+length-1 dizenin içinde kalan her başlangıç konumu i için iki uçtaki harfi kontrol et.
Harfler eşleşiyorsa ve uzunluk en fazla 2 ise veya pal[i+1][j-1] true ise pal[i][j] hücresini işaretle.
İşaretli bir hücrenin uzunluğu mevcut en iyi uzunluğu aşarsa i değerini ve uzunluğu kaydet.
En iyi başlangıç konumundaki alt dizeyi döndür.

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]

Her merkezin etrafında genişletin

Sezgi

Her palindromun bir merkezi vardır. "anana" gibi tek uzunluklu bir palindromda merkez bir harftir; "abba" gibi çift uzunluklu bir palindromda ise ortadaki iki harfin arasındaki boşluktur. Uzunluğu n olan bir dizgede n harf ve n-1 boşluk bulunur, yani 2n-1 olası merkez vardır.

Bir merkezden başlayarak iki harf eşleştiği sürece her iki tarafta da birer harf dışarı doğru ilerleyin. Her adım, iki harf daha uzun bir palindrom olduğunu gösterir. İlk uyuşmazlık veya dizgenin kenarı ilerleyişi bitirir; bu merkezi paylaşan daha uzun bir palindrom olamaz, çünkü böyle bir palindrom uyuşmayan çifti de içerirdi. Dolayısıyla dışarı doğru yapılan tek bir ilerleyiş, her merkezin çevresindeki en uzun palindromu bulur; bunların en uzunu da yanıttır.

"bananas" dizgesinde, 3. indeksteki a harfinden başlayın. 2. ve 4. indekslerdeki harfler n, 1. ve 5. indekslerdeki harfler a'dır; 0. ve 6. indekslerdeki harfler ise b ve s olduğundan ilerleyiş 5 uzunluğunda sona erer. Başlangıç indeksi 3 - (5-1)/2 = 1 olur ve bu da "anana" dizgesini verir. Aşağı yuvarlanmış center - (length-1)/2 biçimindeki aynı formül, boşluk merkezleri için de işe yarar.

Merkezlerde soldan sağa ilerleyin ve en iyiyi yalnızca uzunluk kesin olarak daha büyükse değiştirin. Eşit uzunluktaki iki palindromun paritesi aynıdır ve daha erken merkezli olan daha erken başlar; bu yüzden soldaki kazanır. En kötü durum, aynı harfin tekrarlandığı bir dizgedir: her merkez daha yakın olan kenara kadar ilerler. n = 2000 için bu, yaklaşık n²/2 = 2 × 10^6 adım demektir ve gereken bellek birkaç tam sayıdır.

Algoritma

expand(left, right) fonksiyonunu yaz: her iki indeks de dizenin içindeyken ve harfler eşleşirken left değerini azaltıp right değerini artır. right-left-1 değerini döndür.
0'dan n-1'e kadar her merkez için expand(center, center) ve expand(center, center+1) değerlerinden büyük olanı al.
Bu uzunluk en iyi uzunluğu aşarsa, en iyi başlangıç değerini aşağı yuvarlanmış center - (length-1)/2 olarak, en iyi uzunluğu ise bu değer olarak ayarla.
En iyi başlangıç konumunda, en iyi uzunluktaki alt dizgeyi döndür.

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]

Tuzaklar ve uç durumlar

Fikir kısa, bu yüzden hatalar ayrıntılarda gizlenir: çift uzunluklu palindromların merkezleri, ilerlemeden sonraki uzunluk, eşitlik kuralı ve dilimleme.

Yalnızca harflerin etrafında genişletmek, çift uzunluklu her palindromu kaçırır. "abba" için "abba" yerine "a" döndürür.
İlerleme, her iki ucun bir adım ötesinde durur; bu nedenle palindrom s[left+1..right-1], uzunluğu ise right-left-1 olur. right-left+1 kullanmak eşleşmeyen iki harf ekler.
Eşit uzunlukta en iyiyi değiştirmek, en sağdaki palindromu döndürür: "xyzzyabba" için "yzzy" yerine "abba".
Bir aralık merkezinde center - length/2 bir fazla sola gider. "xyzzyabba" içinde 2. indeksten sonraki aralığın uzunluğu 4'tür ve başlangıç 2 - (4-1)/2 = 1 olur; 0 değil.
Dilimleme API'leri farklıdır: C++ substr ve C# Substring uzunluk alırken, JavaScript substring ve Java substring bitiş indeksi alır.
Tabloda satırları başlangıç indeksine göre 0'dan yukarı doldurmak, pal[i+1][j-1] doldurulmadan önce okunmasına yol açar. Uzunluğa göre doldurun veya başlangıçları sondan başlayarak ilerletin.

Sıkça sorulan sorular4

Longest Palindromic Substring'in zaman karmaşıklığı nedir?

Merkezlerin etrafında genişletme O(n²) zaman ve O(1) ek bellek alır. Tablo yaklaşımı da O(n²) zaman alır ancak O(n²) bellek gerektirir ve her alt dizenin kontrol edilmesi O(n³) sürer. Manacher algoritması O(n) değerine ulaşır, ancak mülakat yapanlar bunu nadiren bekler.

Merkez etrafında genişletme neden 2n-1 merkez kullanır?

Tek sayıda harften oluşan bir palindromun ortasında bir harf, çift sayıda harften oluşan bir palindromun ise eşit iki harf arasında bir boşluk bulunur. n harften oluşan bir dizgede n harf ve komşu harfler arasında n-1 boşluk vardır. Yalnızca harflerden başlayarak genişletmek, "abba" gibi palindromları gözden kaçırır.

Manacher algoritması nedir?

Her merkezin çevresindeki en uzun palindromu toplam O(n) sürede bulur. Şimdiye kadar sağa en çok uzanan palindromu tutar ve onun içindeki bir merkez, karşılık gelen simetrik merkezin yanıtından başlar; böylece hiçbir harf en baştan yeniden karşılaştırılmaz. Adını bilmekte fayda var; merkezden genişletme, mülakat yapanların genellikle beklediği çözümdür.

En uzun palindromik alt dize, en uzun palindromik alt diziden nasıl farklıdır?

Alt dize, art arda gelen harflerden oluşan bir dizidir; alt dizi ise harfleri atlayabilir. "character" içinde en uzun palindromik alt dize "ara" iken, "carac" uzunluğu 5 olan palindromik bir alt dizidir. Alt dizi sürümü, iki uç farklı olduğunda uçlardan birini çıkaran (i, j) üzerinde bir tablo kullanılarak çözülür.

Python

def longestPalindrome(s):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

s = "bananas"

Beklenen

"anana"

Longest Palindromic Substring

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her alt dizgeyi kontrol et

Uzunluğa göre palindromlar tablosu

Her merkezin etrafında genişletin

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler