Longest Palindromic Substring

+10

Kamu mendapatkan string s yang terdiri dari huruf kecil bahasa Inggris. Kembalikan substring palindrom terpanjangnya: rangkaian huruf berurutan terpanjang yang dibaca sama dari depan maupun dari belakang. Jika beberapa substring memiliki panjang yang sama, kembalikan substring yang dimulai paling kiri.

Fungsi

longestPalindrome(s: string) → string

sstring: string huruf kecil yang akan dicari
Mengembalikanstring: substring palindrom terpanjang dari s, yang paling kiri jika ada beberapa yang sama panjang

Batasan

1 ≤ s.length ≤ 2000
s hanya berisi huruf kecil bahasa Inggris.
Jika beberapa palindrom memiliki panjang terpanjang yang sama, jawabannya adalah palindrom dengan indeks awal terkecil.

Contoh

Input: s = "bananas"
Output: "anana"
Penjelasan: "anana" dibaca sama dari kedua arah dan terdiri dari 5 huruf. Setiap bagian yang lebih panjang tidak cocok di kedua ujungnya: "banana" (b, a), "ananas" (a, s), dan "bananas" (b, s).

Input: s = "xyzzyabba"
Output: "yzzy"
Penjelasan: "yzzy" dan "abba" sama-sama merupakan palindrom dengan panjang 4, dan tidak ada yang lebih panjang. "yzzy" dimulai pada indeks 1, sebelum "abba" pada indeks 5, jadi itulah yang menang saat seri.

Input: s = "abcd"
Output: "a"
Penjelasan: Tidak ada dua huruf yang sama, jadi setiap palindrom hanya terdiri dari satu huruf. Huruf paling kiri adalah "a".

Pertanyaan lanjutan

Bisakah kamu menemukan jawabannya dalam waktu O(n)?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Palindrom simetris di sekitar bagian tengahnya: satu huruf untuk panjang ganjil, seperti "anana", atau celah di antara dua huruf yang sama untuk panjang genap, seperti "abba". Perluas setiap palindrom ke arah luar dari bagian tengahnya, dan setiap perbandingan memperluas palindrom yang sudah kamu temukan: waktu O(n²) dan memori tambahan O(1), dibandingkan dengan O(n³) untuk menguji setiap substring secara terpisah.

Periksa setiap substring

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Tetapkan awal i dan akhir j, lalu bandingkan huruf dari kedua ujung ke arah tengah sampai ada dua huruf yang berbeda atau kedua penunjuk bertemu. Mencoba semua substring n(n+1)/2 tidak mungkin melewatkan jawabannya. Dengan memeriksa titik awal dari kiri ke kanan, mengganti yang terbaik hanya jika palindromnya lebih panjang akan mempertahankan yang paling kiri.

Setiap pengujian dapat menelusuri setengah substring. Untuk 2000 salinan a, setiap substring adalah palindrom: sekitar n³/12 ≈ 6.7 × 10^8 perbandingan huruf.

Algoritma

Mulai dengan menganggap huruf pertama sebagai yang terbaik: posisi awal 0, panjang 1.
Untuk setiap posisi awal i dan setiap posisi akhir j ≥ i, bandingkan huruf dari kedua ujung ke arah tengah sampai hurufnya berbeda atau kedua pointer bertemu.
Jika tidak ada pasangan huruf yang berbeda dan j-i+1 lebih panjang daripada panjang terbaik, catat i dan panjang tersebut.
Kembalikan substring pada posisi awal terbaik dengan panjang terbaik.

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]

Tabel palindrom berdasarkan panjang

Intuisi

Menguji "anana" membandingkan a dengan a, lalu n dengan n, dan perbandingan kedua itu adalah seluruh pengujian untuk "nan". Simpan setiap jawaban: s[i..j] adalah palindrome jika kedua ujungnya cocok dan s[i+1..j-1] juga palindrome.

Isi tabel pal[i][j] berdasarkan panjang. Satu huruf adalah palindrome, dua huruf menjadi palindrome jika keduanya cocok, dan sel yang lebih panjang membaca sel yang dua huruf lebih pendek, yang sudah diisi. Dalam "bananas", pal[1][5] bernilai benar karena s[1] dan s[5] sama-sama a, dan pal[2][4] ("nan") bernilai benar. Untuk setiap panjang, posisi awal bergerak dari kiri ke kanan, jadi palindrome pertama dengan panjang rekor adalah yang paling kiri.

Sekitar n²/2 sel dengan biaya O(1) untuk setiap sel menghasilkan waktu O(n²). Biayanya adalah memori: 4 × 10^6 sel untuk n = 2000.

Algoritma

Buat tabel berukuran n × n bernama pal, dengan semua nilainya false.
Untuk setiap panjang dari 1 hingga n, dan setiap titik awal i dengan titik akhir j = i+length-1 yang masih berada di dalam string, bandingkan s[i] dan s[j].
Tandai pal[i][j] jika keduanya cocok dan panjangnya paling banyak 2 atau pal[i+1][j-1] bernilai true.
Jika panjang sel yang ditandai melebihi yang terbaik saat ini, catat i dan panjangnya.
Kembalikan substring yang dimulai dari posisi terbaik.

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]

Kembangkan dari setiap pusat

Intuisi

String yang terdiri dari n huruf memiliki n pusat huruf dan n-1 pusat celah, jadi totalnya 2n-1. Dari sebuah pusat, bergerak ke luar selama kedua huruf cocok. Ketidakcocokan pertama, atau tepi, mengakhiri penelusuran, dan tidak ada yang lebih panjang yang dapat memiliki pusat tersebut, karena palindrom itu akan memuat pasangan huruf yang tidak cocok. Jadi, satu penelusuran untuk setiap pusat akan menemukan palindrom terpanjang dengan pusat tersebut.

Dalam "bananas", penelusuran dari indeks 3 mencocokkan n dengan n dan a dengan a, lalu berhenti pada b dan s: panjangnya 5, awalnya 3 - (5-1)/2 = 1, jadi hasilnya "anana". Dua palindrom dengan panjang yang sama memiliki paritas yang sama, jadi pusat yang lebih awal memiliki posisi awal yang lebih awal. Telusuri pusat dari kiri ke kanan dan ganti yang terbaik hanya jika panjangnya benar-benar lebih besar.

Kasus terburuk adalah satu huruf yang diulang: sekitar n²/2 = 2 × 10^6 langkah untuk n = 2000, dengan beberapa bilangan bulat dalam memori.

Algoritma

Tulis expand(left, right): selama kedua indeks berada di dalam string dan hurufnya cocok, geser left ke bawah dan right ke atas. Kembalikan right-left-1.
Untuk setiap titik tengah dari 0 hingga n-1, ambil nilai yang lebih besar dari expand(center, center) dan expand(center, center+1).
Jika panjang tersebut melebihi yang terbaik sejauh ini, tetapkan posisi awal terbaik ke center - (length-1)/2, dibulatkan ke bawah, dan panjang terbaik ke nilai tersebut.
Kembalikan substring pada posisi awal terbaik dengan panjang terbaik.

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]

Jebakan dan kasus tepi

Ekspansi hanya dari huruf akan melewatkan semua palindrom dengan panjang genap: "abba" menghasilkan "a".
Penelusuran berhenti satu langkah melewati setiap ujung, jadi panjangnya adalah right-left-1. Menggunakan right-left+1 akan menghitung dua huruf yang tidak cocok.
Mengganti palindrom terbaik saat panjangnya sama akan menghasilkan palindrom paling kanan: "abba", bukan "yzzy", untuk "xyzzyabba".
Untuk pusat berupa celah, center - length/2 terlalu jauh satu posisi ke kiri. Dalam "xyzzyabba", celah setelah indeks 2 menghasilkan panjang 4 dan posisi awal 2 - (4-1)/2 = 1, bukan 0.
Mengisi tabel berdasarkan posisi awal dari 0 ke atas akan membaca pal[i+1][j-1] sebelum nilainya ditetapkan. Isi tabel berdasarkan panjang, atau telusuri posisi awal dari akhir.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu dari substring palindrom terpanjang?

Memperluas dari pusat membutuhkan waktu O(n²) dan memori tambahan O(1). Tabel palindrom juga membutuhkan waktu O(n²), tetapi menyimpan n² sel, sedangkan memeriksa setiap substring satu per satu membutuhkan waktu O(n³).

Sebaiknya kamu menggunakan dynamic programming atau memperluas dari tengah?

Perluas dari tengah. Keduanya membutuhkan waktu O(n²), tetapi tabel menyimpan 4 × 10^6 sel untuk n = 2000, sedangkan perluasan hanya menyimpan beberapa bilangan bulat. Perluasan juga berhenti saat menemukan ketidakcocokan pertama, sehingga string dengan sedikit palindrom membutuhkan jauh lebih sedikit dari n² langkah.

Apa perbedaan substring palindromik terpanjang dengan subsekuens palindromik terpanjang?

Substring adalah rangkaian huruf yang berurutan, sedangkan subsequence dapat melewati huruf. Dalam "character", substring palindromik terpanjang adalah "ara", tetapi "carac" adalah subsequence palindromik dengan panjang 5. Versi subsequence menggunakan tabel untuk (i, j) yang menghapus salah satu ujung saat kedua ujungnya berbeda.

def longestPalindrome(s):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

s = "bananas"

Output yang diharapkan

"anana"

Longest Palindromic Substring

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Periksa setiap substring

Tabel palindrom berdasarkan panjang

Kembangkan dari setiap pusat

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa