Palindrome Partitioning

Q: Palindrom Bölümlemenin zaman karmaşıklığı nedir?

Eşit harflerden oluşan bir dizgede, en fazla 2n-1 karakter uzunluğundaki tüm 2^(n-1) bölme birer yanıttır: O(n × 2^n) . Yanıtı yazmak da aynı maliyete sahip olduğundan hiçbir yöntem bunu aşamaz. Palindrom tablosu O(n²) zaman ve alan, özyineleme ise O(n) ekler.

Q: Bir dizenin kaç tane palindrom bölümlendirmesi olabilir?

En fazla 2^(n-1) ; n-1 aralıktan hangilerinin kesileceğini seçmenin her bir yolu için bir tane. Aynı harflerden oluşan bir dize bu sınıra ulaşır: 11 harf için 1.024 bölme. Tekrarlanan harf içermeyen bir dizenin tam olarak bir bölmesi vardır; her harf tek başınadır.

Q: Palindrom Bölümleme dinamik programlama mı yoksa geri izleme mi?

İkisini de kullanır. En fazla 2^(n-1) bölmeyi listelemek, her bölmeyi parça parça oluşturan bir arama gerektirir: geri izleme. Dinamik programlama, aramanın okuduğu palindromik alt dizelerin evet/hayır tablosunu sağlar; bu tablo bir kez O(n²) sürede doldurulur.

OrtaGeri izleme Dinamik programlama

+10

Palindrom, soldan sağa ve sağdan sola aynı şekilde okunur. s dizgesini, her parçası bir palindrom olacak şekilde bir veya daha fazla parçaya böl ve bunu yapmanın tüm yollarını döndür.

Her bölmeyi parçalarını sırayla | ile birleştirerek yaz: aab dizgesini a, a ve b olarak bölmek a|a|b sonucunu verir. Bölmeleri, karakter kodlarını karşılaştırarak artan sırada döndür; böylece |, tüm küçük harflerden sonra gelir.

Fonksiyon

partition(s: string) → string-array

sstring: kesilecek küçük harflerden oluşan dize
Döndürürstring-array: s'nin palindromlara bölünmelerinin her biri, parçaların arasına | konularak, artan sırada

Kısıtlar

1 ≤ s.length ≤ 11
s yalnızca küçük harfli İngilizce harfler içerir.
11 aynı harften oluşan bir dizenin 1,024 bölünmesi vardır; bu en büyük yanıttır.

Örnekler

Girdi: s = "aab"
Çıktı: ["aa|b", "a|a|b"]
Açıklama: Yalnızca aa|b ve a|a|b parçalarının tümü palindromiktir; a|ab, ab parçasında başarısız olur. aa|b önce sıralanır: ikinci karakterde, diğerinde | varken onda a vardır ve | tüm harflerden sonra sıralanır.

Girdi: s = "abba"
Çıktı: ["abba", "a|bb|a", "a|b|b|a"]
Açıklama: abba kendi başına bir palindromdur, bu yüzden bölünmemiş dize bir bölünmedir ve ilk sırada yer alır: ikinci karakteri bir harftir. a|bb|a, a|b|b|a öğesinden önce gelir: dördüncü karakterde, diğerinde | varken bunda b vardır.

Ek soru

Uzunluğu 2,000'e kadar olan dizgiler için s'yi palindromlara ayıran en az kesme sayısını bulabilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Harfler arasındaki n-1 boşluğun her biri kesilir ya da kesilmez; dolayısıyla 2^(n-1) bölme vardır ve bunların tümü yanıt olabilir. Çıktı boyutunu küçültemezsiniz, ancak başarısız olan bölmeleri atlayabilirsiniz: her bölmeyi soldan sağa oluşturun, yalnızca palindromik parçaları ayırın ve bir kez doldurulmuş bir tablodan palindromları okuyun.

Her kesim kümesini dene

Sezgi

Bölmeleri 0'dan 2^(n-1)-1'e kadar tam sayılarla numaralandır; her bit, bir boşluğun kesilip kesilmediğini belirtir. Her parçası palindrom olan bir sayının bölmesini tut.

İlk boşluğa en yüksek bit karşılık gelirse, sayıları artan sırayla saymak bölmeleri de artan sırada listeler. İki sayı için, farklı oldukları en yüksek bit, birinin kestiği, diğerinin kesmediği en erken boşluğu gösterir. Ondan önce dizeler eşittir; o boşlukta küçük sayıda bir harf, büyük sayıda ise her harften sonra sıralanan | bulunur. aab için 1, aa|b sonucunu; 3 ise a|a|b sonucunu verir.

11 harfte bu, her biri 11 harften oluşan 1.024 maske demektir. Gereksiz iş, elenen bölmelerdedir: abcdefghijk, tek bir yanıt bulmak için 1.024'ünün tamamını oluşturur.

Algoritma

mask üzerinde 0'dan 2^(n-1)-1'e kadar döngü kur.
Harfleri ilerleyerek gez; i son indeksse veya mask'in n-2-i bit'i ayarlanmışsa i harfinden sonra bir parçayı bitir.
Her parçayı, içe doğru ilerleyen iki işaretçiyle kontrol et.
Tüm parçalar birer palindromsa parçaları | ile birleştir ve dizgeyi yanıta ekle.
Yanıtı döndür; ilk boşluk en yüksek bit olduğu için zaten sıralıdır.

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

Palindrom tablosuyla geri izleme

Sezgi

İlk parça palindromik bir ön ektir: s[0..end]. Geriye kalanı bölmek, end+1 konumundan başlayan aynı problemdir. Bu nedenle backtrack(start), s[start..end] bir palindrom olduğunda her end değerini dener, parçayı ekler, özyinelemeli olarak devam eder ve parçayı kaldırır. Tek bir harf palindrom olduğundan her dal bir yanıtta sona erer; dolayısıyla iş miktarı çıktı boyutunu izler: abcdefghijk için arama tek bir yol izler.

s[start..end] ifadesinin palindrom olup olmadığı birçok dalda gündeme gelir; bu yüzden sonucu bir tablodan oku: s[i..j], s[i] == s[j] olduğunda ve iç kısım s[i+1..j-1] palindrom olduğunda ya da parça en fazla 2 harf içerdiğinde palindromdur.

end değerini son indexten başlayarak denemek, sıralı çıktı verir. İlk parçaları farklı olan iki bölme, kısa parçanın sonuna kadar aynı sıradadır; orada kısa parçada |, uzunsa bir harf bulunur, bu nedenle ilk parçası daha uzun olan önce sıralanır.

Algoritma

pal[i][j] değerini, i için n-1 değerinden 0'a doğru doldurun: s[i] == s[j] ve ya j-i < 2 ya da pal[i+1][j-1].
backtrack(start) yazın. start değeri n'e eşitse, geçerli parçaları | ile birleştirin ve dizgeyi kaydedin.
Aksi durumda end değerini n-1'den start'a doğru döngüye alın ve pal[start][end] değilse bu değeri atlayın.
s[start..end] değerini parçalara ekleyin, backtrack(end+1) çağrısını yapın, ardından parçayı kaldırın.
backtrack(0) çağrısını yapın ve önceden sıralanmış bölmeleri döndürün.

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

Tuzaklar ve uç durumlar

Önce en kısa parçayı denemek. Parçalar doğru ama sıralama yanlış: a|a|b, aa|b'den önce geliyor.
Sonda, dil veya yerel ayar kurallarına uyan bir karşılaştırmayla sıralamak; bu, | karakterini harflerden önce sıralayabilir. Karakter kodlarını karşılaştırın veya parçaları sıralı biçimde oluşturun.
Palindrom tablosunu i artacak şekilde doldurmak. Böylece pal[i+1][j-1] hesaplanmadan önce okunur; i değerini n-1'den başlayarak geriye doğru doldurun.
Dahilî bir end değerini, hariç tutmalı bir alt dize bitişiyle karıştırmak. s[start..end] parçasında end-start+1 harf vardır.
Birleştirilmiş dize yerine paylaşılan parça listesini kaydetmek. Arama bu listeyi değiştirmeye devam eder, dolayısıyla kaydedilen her öğe aynı olur.

Sıkça sorulan sorular3

Palindrom Bölümlemenin zaman karmaşıklığı nedir?

Eşit harflerden oluşan bir dizgede, en fazla 2n-1 karakter uzunluğundaki tüm 2^(n-1) bölme birer yanıttır: O(n × 2^n). Yanıtı yazmak da aynı maliyete sahip olduğundan hiçbir yöntem bunu aşamaz. Palindrom tablosu O(n²) zaman ve alan, özyineleme ise O(n) ekler.

Bir dizenin kaç tane palindrom bölümlendirmesi olabilir?

En fazla 2^(n-1); n-1 aralıktan hangilerinin kesileceğini seçmenin her bir yolu için bir tane. Aynı harflerden oluşan bir dize bu sınıra ulaşır: 11 harf için 1.024 bölme. Tekrarlanan harf içermeyen bir dizenin tam olarak bir bölmesi vardır; her harf tek başınadır.

Palindrom Bölümleme dinamik programlama mı yoksa geri izleme mi?

İkisini de kullanır. En fazla 2^(n-1) bölmeyi listelemek, her bölmeyi parça parça oluşturan bir arama gerektirir: geri izleme. Dinamik programlama, aramanın okuduğu palindromik alt dizelerin evet/hayır tablosunu sağlar; bu tablo bir kez O(n²) sürede doldurulur.

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

Test #1

Test #2

Argüman

s = "aab"

Beklenen Çıktı

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