Edit Distance

Q: Yalnızca sayıyı değil, düzenlemelerin listesini nasıl alırsınız?

Tablonun tamamını tutun ve dp[n][m] noktasından geriye doğru ilerleyin. Harfler eşleşiyorsa düzenleme yapmadan çapraz ilerleyin. Aksi takdirde değeri bir eksik olan komşuya ilerleyin: çapraz ilerlemek değiştirme, yukarı ilerlemek silme, sola ilerlemek eklemedir. dp[0][0] noktasında durun ve düzenlemeleri tersten okuyun. İki satırlı sürüm bunu tek başına yapamaz, çünkü önceki satırları atmıştır.

Q: Düzenleme Mesafesi tek bir diziyle çözülebilir mi?

Evet. Tek bir row dizisini yerinde, soldan sağa doldur. row[j] değerinin üzerine yazmadan önce bu değer hâlâ üst satırdaki değeri tutar ve row[j-1] zaten geçerli satırı tutmaktadır. Kaybettiğin tek değer köşegendeki değerdir; bu yüzden onu bir değişkende sakla: yazmadan önce eski row[j] değerini kaydet ve j + 1 için köşegen olarak kullan.

ZorDinamik programlama

+10

Sana iki kelime verilir: word1 ve word2. Bir düzenleme, word1 kelimesini üç yoldan biriyle değiştirir: herhangi bir yere bir harf eklemek, bir harfi silmek veya bir harfi başka bir harfle değiştirmek. word1 kelimesini word2 kelimesine dönüştürmek için gereken en az düzenleme sayısını döndür.

Fonksiyon

minDistance(word1: string, word2: string) → integer

word1string: düzenlediğiniz kelime
word2string: ulaşmak kelimesi
Döndürürinteger: word1'i word2'ye dönüştüren en az sayıda ekleme, silme ve değiştirme

Kısıtlar

1 ≤ word1.length ≤ 500
1 ≤ word2.length ≤ 500
Her iki sözcük de yalnızca küçük İngilizce harfler içerir.

Örnekler

Girdi: word1 = "spot"word2 = "stop"
Çıktı: 2
Açıklama: p harfini t ile, t harfini de p ile değiştirin: spot, stot olur, ardından stop. Sözcükler iki yerde farklı olduğu ve ekleme ya da silme uzunluğu değiştireceği için tek bir düzenleme yeterli değildir.

Girdi: word1 = "garden"word2 = "ardent"
Çıktı: 2
Açıklama: arden elde etmek için g harfini silin, ardından sona t ekleyerek ardent elde edin. Harfleri tek tek değiştirmek 6 maliyetine yol açardı, çünkü iki kelime her konumda farklıdır.

Girdi: word1 = "rain"word2 = "shine"
Çıktı: 3
Açıklama: shin elde etmek için r yerine s, a yerine h koy, ardından e ekle. İki düzenlemeyle bunu yapamazsın: r ve a, shine içinde bulunmadığından, her biri kelimeyi uzatmayan bir düzenleme gerektirir ve kelimenin yine de bir harf uzaması gerekir.

Gönderirken +21 gizli test

Ek soru

Yalnızca kaç tane olduklarını değil, en kısa düzenleme listesini de döndürebilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Düzenlemeler birbirini etkiler, bu yüzden sözcükleri konum konum düzeltemezsiniz: garden ve ardent altı konumun tamamında farklıdır, ancak g silinip geri kalan her şey sola kayınca iki düzenleme yeterli olur. Bu düğümü çözen fikir, her sözcüğün yalnızca son harfine bakmaktır. İki harf ya zaten aynıdır ya da tam olarak üç düzenlemeden biri onları aynı hâle getirir ve her seçenek, daha kısa önekler üzerinde aynı problemi bırakır. (n+1) × (m+1) yanıttan oluşan bir tablo, her önek çiftini bir kez çözer ve tablonun iki satırı yeterlidir.

Özyinelemeyi kullanarak üç düzenlemenin tümünü deneyin

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

Sezgi

edits(i, j), word1[i:] son ekini word2[j:] son ekine dönüştürmek için gereken en az düzenleme sayısı olsun. İki son ekin ilk harflerine bak. Eşitlerse onları koru ve her iki indisi ilerlet: eşleşen bir harfin düzenlenmesi gerekmez ve o harfi düzenlemek için harcanan bir düzenleme, planı uzatmadan harfi koruyacak şekilde değiştirilebilir.

Farklılarsa, bir düzenlemenin word1[i] harfini ele alması ya da word2[j] harfini üretmesi gerekir ve bunun tam olarak üç yolu vardır. word1[i] harfini word2[j] ile değiştir ve her iki indisi ilerlet: edits(i+1, j+1). word1[i] harfini sil ve yalnızca i ilerlesin: edits(i+1, j). word2[j] harfini onun önüne ekle ve yalnızca j ilerlesin: edits(i, j+1). Yanıt, bu üçünün en düşük maliyetlisinin 1 fazlasıdır. word1 bittiğinde word2'nin geri kalanını ekle; bunun maliyeti m - j olur. word2 bittiğinde word1'in geri kalanını sil; bunun maliyeti n - i olur.

Yavaş olmasının nedeni, her uyuşmazlıkta üç çağrı yapılmasıdır. Ortak harfi olmayan, 15 harflik iki sözcük için bu yaklaşık 6.7 × 10^10 çağrı demektir ve büyük testlerde her sözcük 500 harflidir. Oysa yalnızca (n+1) × (m+1) farklı (i, j) çifti vardır; dolayısıyla hemen hemen her çağrı, daha önce yapılmış bir çağrıyı tekrarlar.

Algoritma

i ve j konumlarından başlayan son ekler için edits(i, j) yazın.
i, word1 dizgesinin sonunu geçtiyse m - j döndürün; j, word2 dizgesinin sonunu geçtiyse n - i döndürün.
word1[i] == word2[j] ise edits(i+1, j+1) döndürün.
Aksi takdirde, değiştirme, silme ve ekleme işlemleri için 1 + min(edits(i+1, j+1), edits(i+1, j), edits(i, j+1)) döndürün.
Yanıt edits(0, 0) değeridir.

def minDistance(word1, word2):
    n, m = len(word1), len(word2)

    def edits(i, j):
        # Fewest edits to turn word1[i:] into word2[j:]
        if i == n:
            return m - j  # insert the rest of word2
        if j == m:
            return n - i  # delete the rest of word1
        if word1[i] == word2[j]:
            return edits(i + 1, j + 1)
        return 1 + min(edits(i + 1, j + 1),  # replace word1[i] with word2[j]
                       edits(i + 1, j),      # delete word1[i]
                       edits(i, j + 1))      # insert word2[j]

    return edits(0, 0)

Önekler tablosunu doldur

Sezgi

Durum. dp[i][j], word1'in ilk i harfini word2'nin ilk j harfine dönüştürmek için gereken en az düzenleme sayısı olsun. 0 indeksi, boş bir öneki ifade eder.

Geçişler. İki önekin son harflerini, word1[i-1] ve word2[j-1] değerlerini karşılaştırın. Eşitlerse, bu harfleri koruyun: dp[i][j] = dp[i-1][j-1]; bu, çapraz olarak yukarıdaki ve soldaki hücredir. Eşit değillerse, bir düzenleme maliyeti ekleyip üç komşudan en ucuz olanı seçin. Çapraz hücre dp[i-1][j-1], word1[i-1] harfini word2[j-1] ile değiştirmek anlamına gelir. Yukarıdaki hücre dp[i-1][j], word1[i-1] harfini silmek anlamına gelir. Soldaki hücre dp[i][j-1], sona word2[j-1] harfini eklemek anlamına gelir.

Taban satırı ve sütunu. Birçok tablo probleminden farklı olarak, bunlar sıfır değildir. i harfi boş bir öneke dönüştürmek için i silme gerekir; dolayısıyla dp[i][0] = i. Hiçbir şeyden j harf oluşturmak için j ekleme gerekir; dolayısıyla dp[0][j] = j. Her hücre yukarıdaki, solundaki ve çapraz hücreyi okur; bu yüzden satır satır, soldan sağa doldurmak, bu hücrelerin hazır olmasını sağlar. Yanıt dp[n][m] değeridir.

İşte spot sözcüğünü stop sözcüğüne dönüştürme tablosu; sütunlar "", s, st, sto, stop öneklerine karşılık gelir. "" satırı [0, 1, 2, 3, 4], s satırı [1, 0, 1, 2, 3], sp satırı [2, 1, 1, 2, 2], spo satırı [3, 2, 2, 1, 2] ve spot satırı [4, 3, 2, 2, 2] değerlerini içerir. Birkaç hücreyi inceleyelim. s ile s eşleşir, bu nedenle çaprazdaki 0 değerini kopyalar. sp ile st eşleşmez: komşu hücreleri çaprazda 0, yukarıda 1 ve solda 1 değerlerini içerir; dolayısıyla sonuç 1 + 0 = 1 olur, yani bir değiştirme gerekir. spo ile sto, o harfinde eşleşir ve o hücredeki 1 değerini kopyalar. Son hücrede, spot ile stop karşılaştırılırken t ile p karşılaştırılır: komşu hücrelerinin değerleri 1, 2 ve 2'dir; dolayısıyla yanıt 1 + 1 = 2 olur.

Tabloda (n+1) × (m+1) hücre vardır ve her hücrede sabit miktarda işlem yapılır; 500 harfli iki sözcük için yaklaşık 2.5 × 10^5 adımdır. Önbelleğe alınmış bir özyinelemeli çözüm aynı hücreleri doldurur, ancak n + m çağrı derinliğine kadar özyinelemeye gidebilir; bu da Python'ın varsayılan 1000 sınırını aşar.

Algoritma

(n+1) × (m+1) hücreden oluşan bir dp tablosu oluştur.
Her i için dp[i][0] = i ve her j için dp[0][j] = j değerini ayarla.
i için 1'den n'ye ve j için 1'den m'ye kadar, word1[i-1] == word2[j-1] ise dp[i][j] = dp[i-1][j-1] değerini ayarla.
Aksi takdirde dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) değerini ayarla.
dp[n][m] değerini döndür.

def minDistance(word1, word2):
    n, m = len(word1), len(word2)
    # dp[i][j]: fewest edits to turn the first i letters of word1 into the first j of word2
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = i  # delete all i letters
    for j in range(m + 1):
        dp[0][j] = j  # insert all j letters
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j - 1],  # replace
                                   dp[i - 1][j],      # delete word1[i-1]
                                   dp[i][j - 1])      # insert word2[j-1]
    return dp[n][m]

Yalnızca iki satır tutun

Sezgi

i satırı yalnızca i-1 satırını ve kendi satırında solundaki hücreleri okur. Bir satır tamamlandığında, üstündeki satırlar bir daha okunmaz. İki dizi tut: tamamlanan satır için prev ve doldurmakta olduğun satır için cur; her satırdan sonra bunları yer değiştir. Geçişler değişmez: çapraz hücre prev[j-1], üst hücre prev[j] ve sol hücre cur[j-1].

Taban sütunu ortadan kalkmaz. Artık her satırın ilk elemanında yer alır; bu nedenle i satırını doldurmadan önce cur[0] = i olarak ayarla. 0. satır, taban satırı olan [0, 1, 2, ..., m] ile başlar.

word2 sözcüğünü word1 sözcüğüne dönüştürmek aynı sayıda düzenleme gerektirir; çünkü her ekleme silmeye, her silme de eklemeye dönüşür. Bu nedenle sözcüklerin yerini değiştirebilir ve satırları daha kısa olan sözcük boyunca ilerletebilirsin. Böylece her satır, 251,001 hücreye kadar çıkabilen bir tablo yerine min(n, m) + 1 sayı tutar ve işlem miktarı O(n × m) olarak kalır.

Algoritma

word2, word1'den daha uzunsa, yerlerini değiştir.
prev = [0, 1, ..., m] olarak ayarla; burada m daha kısa olan uzunluktur.
1'den n'ye kadar her i için cur[0] = i olarak ayarla, ardından prev'den köşegeni ve üsttekini, cur'den soldakini okuyarak aynı kuralla cur[1..m] değerlerini doldur.
prev ile cur'ün yerlerini değiştir.
prev[m] değerini döndür.

def minDistance(word1, word2):
    if len(word2) > len(word1):
        word1, word2 = word2, word1  # the rows run along the shorter word
    m = len(word2)
    # prev[j]: fewest edits to turn the previous prefix of word1 into word2[:j]
    prev = list(range(m + 1))
    for i in range(1, len(word1) + 1):
        cur = [i] + [0] * m  # i letters into an empty prefix: delete them all
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j - 1],  # replace
                                 prev[j],      # delete word1[i-1]
                                 cur[j - 1])   # insert word2[j-1]
        prev = cur
    return prev[m]

Tuzaklar ve uç durumlar

Özyineleme bağıntısı kısa olduğundan hataların çoğu temel durumlarda veya hangi komşunun okunduğunda ortaya çıkar.

En uzun ortak alt dizi örneğindeki gibi 0. satırı ve 0. sütunu sıfırlarla doldurmak. abc dizgesini boş bir öneke dönüştürmek 0 değil, 3 silme işlemine mal olur; bu nedenle dp[i][0] değeri i ve dp[0][j] değeri j olmalıdır.
İki satırlı sürümde cur[0] = i atamasını unutmak. İlk hücre iki satır öncesinden kalan bir değeri korur ve ondan sonraki her hücre yanlış olur.
Eşleşme durumunda bir düzenleme işleminin maliyetini eklemek. Harfler eşitse dp[i][j] = 1 + min(...) kullanmak, a harfini a harfine dönüştürmenin maliyetini 1 yapar. Eşleşme durumunda köşegen değeri kopyalayın.
Sol komşuyu cur yerine prev içinden okumak. Sol komşu mevcut satırdadır: word1[:i] zaten word2[:j-1] biçimine dönüştürüldükten sonra word2[j-1] ekleme işlemini temsil eder.
Konumları tek tek karşılaştırmak. Sözcüklerin farklı olduğu konumları saymak, ekleme ve silme işlemlerini göz ardı eder: garden ve ardent için sonuç 6 olurken doğru yanıt 2'dir.
500 harfli sözcükler üzerinde özyinelemeyle önbelleğe alma yapmak. Çağrı derinliği 1000'e ulaşır; bu, Python'ın varsayılan sınırıdır.

Sıkça sorulan sorular4

Edit Distance'in zaman karmaşıklığı nedir?

Tablo çözümü, her önek çifti için sabit miktarda işlemle bir hücre doldurduğundan O(n × m) zamanda çalışır; burada n ve m iki dizenin uzunluklarıdır. Tam tablo için O(n × m) bellek, iki satır kullanıldığında ise O(min(n, m)) bellek kullanır. Tablo kullanmadan yapılan yalın özyineleme üstel zamandadır.

Düzenleme mesafesi, Levenshtein mesafesiyle aynı mıdır?

Evet, bu sürüm Levenshtein mesafesidir: ekleme, silme ve değiştirme işlemlerinin her biri bir birim maliyetlidir. Düzenleme mesafesi, bu yöntemlerin genel adıdır. Diğer yöntemler daha az veya daha fazla düzenlemeye izin verir: yalnızca ekleme ve silme işlemleri n + m - 2 × LCS sonucunu verir, uzunluklar eşitse yalnızca değiştirme işlemleri Hamming mesafesini verir ve yan yana duran iki harfi yer değiştirme işlemi eklenirse Damerau sürümü elde edilir.

Yalnızca sayıyı değil, düzenlemelerin listesini nasıl alırsınız?

Tablonun tamamını tutun ve dp[n][m] noktasından geriye doğru ilerleyin. Harfler eşleşiyorsa düzenleme yapmadan çapraz ilerleyin. Aksi takdirde değeri bir eksik olan komşuya ilerleyin: çapraz ilerlemek değiştirme, yukarı ilerlemek silme, sola ilerlemek eklemedir. dp[0][0] noktasında durun ve düzenlemeleri tersten okuyun. İki satırlı sürüm bunu tek başına yapamaz, çünkü önceki satırları atmıştır.

Düzenleme Mesafesi tek bir diziyle çözülebilir mi?

Evet. Tek bir row dizisini yerinde, soldan sağa doldur. row[j] değerinin üzerine yazmadan önce bu değer hâlâ üst satırdaki değeri tutar ve row[j-1] zaten geçerli satırı tutmaktadır. Kaybettiğin tek değer köşegendeki değerdir; bu yüzden onu bir değişkende sakla: yazmadan önce eski row[j] değerini kaydet ve j + 1 için köşegen olarak kullan.

Python

def minDistance(word1, word2):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

word1 = "spot"
word2 = "stop"

Beklenen

Edit Distance

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Özyinelemeyi kullanarak üç düzenlemenin tümünü deneyin

Önekler tablosunu doldur

Yalnızca iki satır tutun

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler