İki kelimeyi eşlemek için en az silme
Görev tanımı
Problem
İki kelime a ve b verildiğinde, bir adım iki kelimeden birinden tek bir karakter siler. İki kelimeyi özdeş yapmak için gereken en az adımı döndür.
Örnekler
Input: a = "sea", b = "eat"
Output: 2
Neden: sea'dan s'yi, eat'ten t'yi sil, ikisinde de ea kalsın
Input: a = "abcde", b = "ace"
Output: 2
Neden: ace zaten abcde'nin içinde sırasıyla geçiyor, yalnız b ve d gider
Input: a = "abc", b = ""
Output: 3
Neden: edge case: ilk kelimedeki her şey silinmeli
İpuçları
0 / 3
Silmelerden sonra kalan her şey iki kelimede de aynı sırayla görünür. En fazla ne kadarını tutabilirsin?
Tuttuğun karakterler iki kelimenin ortak bir alt dizisini oluşturur. En uzun ortak alt diziyi tutmak olabildiğince az silmek demektir.
En uzun ortak alt dizi uzunluğunu, (i, j) elemanı a'nın ilk i ve b'nin ilk j karakterini kapsayan bir tabloyla hesapla. Cevap len(a) + len(b) eksi bu uzunluğun iki katı.
- Hedef zaman
- O(m · n)
- Hedef alan
- O(m · n)
Çözüm
Kelimeler eşleşene kadar silmek iki kelimenin de alt dizisi (subsequence) olan bir string bırakır; bu yüzden en az silme, en uzun ortak alt diziyi (LCS) tutup her kelimeden geri kalan her şeyi atmaktan gelir. a'nın ilk i ve b'nin ilk j karakteri için tablo elemanı, son karakterler eşleştiğinde çapraz elemanı bir uzatır, eşleşmediğinde de iki kelimeden birinin son karakterini atmanın iyisini alır. Ortak alt dizinin dışındaki her karakter bir kez silinir, bu da len(a) + len(b) - 2 * lcs'yi verir. m ve n uzunluğundaki kelimeler için zaman O(m · n), alan O(m · n).
def min_deletions(a, b):
m, n = len(a), len(b)
lcs = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
lcs[i][j] = lcs[i - 1][j - 1] + 1 # keep the matching pair
else:
lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1])
return m + n - 2 * lcs[m][n] # delete everything not kept
print(min_deletions("sea", "eat")) # -> 2
print(min_deletions("abcde", "ace")) # -> 2
print(min_deletions("abc", "")) # -> 3Kodda değil de fikirde mi takıldın? En uzun ortak alt dizi bunu anlatıyor.