İçeriğe geç

İki kelimeyi eşlemek için en az silme

Kolay#lcs#string-dp~20 dk

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

Hedef zaman
O(m · n)
Hedef alan
O(m · n)

Kodda değil de fikirde mi takıldın? En uzun ortak alt dizi bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case