Edit Distance (Levenshtein): bir kelimeyi diğerine dönüştürmek için gereken minimum ekleme, silme ve değiştirme sayısını bulun.

Bu, iki string üzerinde klasik 2 boyutlu DP problemidir. dp[i][j] = word1'in ilk i karakterini word2'nin ilk j karakterine dönüştürmenin minimum maliyeti.

Geçiş

• Karakterler eşitse: dp[i][j] = dp[i-1][j-1] (işlem gerekmez).
• Değilse: 1 + min(...)
• dp[i-1][j] -> word1[i-1]'i sil
• dp[i][j-1] -> word2[j-1]'i ekle
• dp[i-1][j-1] -> değiştir

Başlangıç: dp[i][0] = i (hepsini sil), dp[0][j] = j (hepsini ekle).

def min_distance(a: str, b: str) -> int:
    m, n = len(a), len(b)
    prev = list(range(n + 1))            # dp[i-1][*]
    for i in range(1, m + 1):
        cur = [i] + [0] * n
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j],      # sil
                                 cur[j - 1],   # ekle
                                 prev[j - 1])  # değiştir
        prev = cur
    return prev[n]

print(min_distance("horse", "ros"))          # 3
print(min_distance("intention", "execution"))  # 5

Karmaşıklık

• Zaman: O(m x n)
• Bellek: tam tablo O(m x n); yukarıdaki gibi yalnızca önceki satırı tutarak O(n).

Gerçek kullanım alanları

Yazım denetimi ve "bunu mu demek istediniz?" önerileri, DNA dizilimi hizalama, diff araçları (LCS tabanlı), fuzzy arama.

İlgili DP soruları

Longest Common Subsequence (aynı tablo yapısı), Word Break, Unique Paths. Hepsinde önce durum, geçiş ve başlangıç değerleri tanımlanır.