Palindrome Partitioning

Q: Apa kompleksitas waktu dari Palindrome Partitioning?

Pada string yang terdiri dari huruf-huruf sama, semua 2^(n-1) pemisahan merupakan jawaban, masing-masing sepanjang hingga 2n-1 karakter: O(n × 2^n) . Tidak ada method yang bisa lebih cepat dari itu, karena menuliskan jawaban membutuhkan waktu yang sama. Tabel palindrom menambah waktu dan ruang sebesar O(n²) , sedangkan rekursi membutuhkan O(n) .

Q: Berapa banyak partisi palindrom yang dapat dimiliki sebuah string?

Paling banyak 2^(n-1) , satu untuk setiap cara memilih celah mana dari n-1 celah yang akan dipotong. String dengan huruf yang sama mencapai batas itu: 1.024 pemisahan untuk 11 huruf. String tanpa huruf berulang memiliki tepat satu pemisahan, setiap huruf berdiri sendiri.

Q: Apakah Pemartisian Palindrom menggunakan pemrograman dinamis atau backtracking?

Keduanya digunakan. Mencantumkan semua pemisahan hingga 2^(n-1) memerlukan pencarian yang menyusun setiap bagian pemisahan satu per satu: backtracking. Pemrograman dinamis menyediakan tabel ya atau tidak untuk substring palindromik yang dibaca oleh pencarian, dan tabel itu diisi sekali dalam O(n²) .

SedangBacktracking Dynamic programming

+10

Palindrom terbaca sama dari kiri ke kanan maupun dari kanan ke kiri. Potong string s menjadi satu bagian atau lebih sehingga setiap bagian merupakan palindrom, lalu kembalikan semua cara untuk melakukannya.

Tulis setiap pemisahan sebagai bagian-bagiannya secara berurutan, dipisahkan dengan |: memotong aab menjadi a, a, dan b menghasilkan a|a|b. Kembalikan pemisahan dalam urutan menaik berdasarkan perbandingan kode karakter, sehingga | berada setelah semua huruf kecil.

Fungsi

partition(s: string) → string-array

sstring: string huruf kecil yang akan dipotong
Mengembalikanstring-array: setiap pembagian s menjadi palindrom, ditulis dengan | di antara bagian-bagiannya, dalam urutan menaik

Batasan

1 ≤ s.length ≤ 11
s hanya berisi huruf kecil bahasa Inggris.
Sebuah string yang terdiri dari 11 huruf yang sama memiliki 1,024 pemisahan, jawaban terbesar.

Contoh

Input: s = "aab"
Output: ["aa|b", "a|a|b"]
Penjelasan: Hanya aa|b dan a|a|b yang memiliki semua bagian palindromik; a|ab gagal pada ab. aa|b berada di urutan pertama: pada karakter kedua, ada a sedangkan yang lainnya memiliki |, yang diurutkan setelah setiap huruf.

Input: s = "abba"
Output: ["abba", "a|bb|a", "a|b|b|a"]
Penjelasan: abba adalah palindrom itu sendiri, jadi string yang tidak dipotong merupakan sebuah pemisahan dan diurutkan terlebih dahulu: karakter keduanya adalah huruf. a|bb|a muncul sebelum a|b|b|a: pada karakter keempat, yang pertama memiliki b, sedangkan yang lain memiliki |.

Pertanyaan lanjutan

Bisakah kamu menemukan jumlah pemotongan paling sedikit untuk membagi s menjadi palindrom, untuk string dengan panjang hingga 2.000?

Petunjuk

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

0 dari 3 dibuka

Solusi

Setiap celah di antara huruf dipotong atau tidak, jadi ada 2^(n-1) pemisahan, dan semuanya bisa menjadi jawaban. Kamu tidak bisa mengurangi ukuran output, tetapi kamu bisa melewati pemisahan yang tidak berhasil: buat setiap pemisahan dari kiri ke kanan, potong hanya bagian yang palindrom, dan baca palindrom dari tabel yang diisi satu kali.

Coba setiap kombinasi potongan

Intuisi

Beri nomor pada pemisahan dengan bilangan bulat dari 0 hingga 2^(n-1)-1, setiap bit menunjukkan apakah satu celah dipotong. Pertahankan nomor pemisahan jika setiap bagiannya adalah palindrome.

Jika celah pertama mendapat bit tertinggi, menghitung ke atas akan mencantumkan pemisahan dalam urutan menaik. Untuk dua angka, bit tertinggi yang berbeda menunjukkan celah paling awal yang dipotong oleh salah satunya, tetapi tidak oleh yang lain. Sebelum celah itu, string-nya sama; pada celah itu, angka yang lebih kecil memiliki sebuah huruf dan angka yang lebih besar memiliki |, yang diurutkan setelah setiap huruf. Untuk aab, 1 menghasilkan aa|b dan 3 menghasilkan a|a|b.

Untuk 11 huruf, jumlahnya adalah 1.024 mask, masing-masing untuk 11 huruf. Pemborosan terjadi pada pemisahan yang ditolak: abcdefghijk membangun semua 1.024 untuk menemukan satu jawaban.

Algoritma

Lakukan perulangan mask dari 0 hingga 2^(n-1)-1.
Telusuri huruf-hurufnya. Akhiri satu bagian setelah huruf i jika i adalah indeks terakhir atau bit n-2-i dari mask bernilai 1.
Periksa setiap bagian dengan dua penunjuk yang bergerak ke arah dalam.
Jika setiap bagian adalah palindrom, gabungkan bagian-bagian itu dengan | dan tambahkan string tersebut ke jawaban.
Kembalikan jawaban. Urutannya sudah benar karena celah pertama adalah bit tertinggi.

def partition(s):
    n = len(s)
    result = []
    # Bit (n-2-i) of mask says whether to cut after s[i]. Counting the
    # masks up from 0 lists the splits in sorted order.
    for mask in range(1 << (n - 1)):
        pieces = []
        start = 0
        for i in range(n):
            if i == n - 1 or (mask >> (n - 2 - i)) & 1:
                pieces.append(s[start:i + 1])
                start = i + 1
        if all(piece == piece[::-1] for piece in pieces):
            result.append("|".join(pieces))
    return result

Backtracking dengan tabel palindrome

Intuisi

Bagian pertama adalah prefix palindromik s[0..end], dan membagi sisanya adalah masalah yang sama mulai dari end+1. Jadi, backtrack(start) mencoba setiap end ketika s[start..end] adalah palindrom, menambahkan bagian tersebut, melakukan rekursi, lalu menghapusnya. Setiap cabang berakhir pada sebuah jawaban, karena satu huruf saja merupakan palindrom, jadi jumlah pekerjaan mengikuti ukuran output: untuk abcdefghijk, pencarian menelusuri satu jalur.

Apakah s[start..end] merupakan palindrom sering diperiksa di banyak cabang, jadi bacalah dari tabel: s[i..j] bernilai satu jika s[i] == s[j] dan bagian dalam s[i+1..j-1] bernilai satu, atau jika bagian tersebut memiliki paling banyak 2 huruf.

Mencoba end dari indeks terakhir ke bawah menghasilkan output yang terurut. Dua pembagian dengan bagian pertama yang berbeda akan sama hingga akhir bagian yang lebih pendek; di sana, bagian yang lebih pendek memiliki | dan bagian yang lebih panjang memiliki huruf, jadi bagian pertama yang lebih panjang diurutkan lebih dahulu.

Algoritma

Isi pal[i][j] untuk i dari n-1 turun hingga 0: s[i] == s[j] dan salah satu dari j-i < 2 atau pal[i+1][j-1].
Tulis backtrack(start). Jika start sama dengan n, gabungkan potongan saat ini dengan | dan simpan string-nya.
Jika tidak, iterasikan end dari n-1 turun hingga start, dan lewati jika pal[start][end] tidak terpenuhi.
Tambahkan s[start..end] ke potongan, panggil backtrack(end+1), lalu hapus potongan tersebut.
Panggil backtrack(0) dan kembalikan hasil pemisahan yang sudah diurutkan.

def partition(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)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1])
    result = []
    parts = []

    def backtrack(start):
        if start == n:
            result.append("|".join(parts))
            return
        # Longest piece first: "|" sorts after every letter, so a longer
        # first piece gives a smaller string and the output stays sorted.
        for end in range(n - 1, start - 1, -1):
            if pal[start][end]:
                parts.append(s[start:end + 1])
                backtrack(end + 1)
                parts.pop()

    backtrack(0)
    return result

Jebakan dan kasus tepi

Mencoba bagian terpendek terlebih dahulu. Pemisahannya benar, tetapi urutannya salah: a|a|b muncul sebelum aa|b.
Mengurutkan di akhir dengan perbandingan yang mengikuti aturan bahasa atau lokal, yang dapat menempatkan | sebelum huruf. Bandingkan kode karakter, atau hasilkan pemisahan dalam urutan yang benar.
Mengisi tabel palindrom dengan i yang terus naik. pal[i+1][j-1] kemudian dibaca sebelum dihitung. Isi i mulai dari n-1 dengan urutan menurun.
Mencampur end yang inklusif dengan akhir substring yang eksklusif. Bagian s[start..end] memiliki end-start+1 huruf.
Menyimpan list bagian yang digunakan bersama, bukan string yang sudah digabungkan. Pencarian terus mengubah list itu, sehingga semua entri yang disimpan akhirnya sama.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari Palindrome Partitioning?

Pada string yang terdiri dari huruf-huruf sama, semua 2^(n-1) pemisahan merupakan jawaban, masing-masing sepanjang hingga 2n-1 karakter: O(n × 2^n). Tidak ada method yang bisa lebih cepat dari itu, karena menuliskan jawaban membutuhkan waktu yang sama. Tabel palindrom menambah waktu dan ruang sebesar O(n²), sedangkan rekursi membutuhkan O(n).

Berapa banyak partisi palindrom yang dapat dimiliki sebuah string?

Paling banyak 2^(n-1), satu untuk setiap cara memilih celah mana dari n-1 celah yang akan dipotong. String dengan huruf yang sama mencapai batas itu: 1.024 pemisahan untuk 11 huruf. String tanpa huruf berulang memiliki tepat satu pemisahan, setiap huruf berdiri sendiri.

Apakah Pemartisian Palindrom menggunakan pemrograman dinamis atau backtracking?

Keduanya digunakan. Mencantumkan semua pemisahan hingga 2^(n-1) memerlukan pencarian yang menyusun setiap bagian pemisahan satu per satu: backtracking. Pemrograman dinamis menyediakan tabel ya atau tidak untuk substring palindromik yang dibaca oleh pencarian, dan tabel itu diisi sekali dalam O(n²).

def partition(s):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

s = "aab"

Output yang diharapkan

["aa|b", "a|a|b"]