Edit distance

word1 va word2 satrlari berilgan. word1 ni word2 ga aylantirish uchun zarur minimal operatsiyalar sonini (Edit Distance) qaytaring.

Ruxsat etilgan amallar: bitta belgini qo'shish, o'chirish yoki boshqasiga almashtirish.

func solve(word1 string, word2 string) int {
    // ...
}

Misollar

Input: word1 = "horse", word2 = "ros"
Output: 3
Tushuntirish: horse -> rorse (h ni r ga) -> rose (r ni o'chirish) -> ros (e ni o'chirish)

Input: word1 = "intention", word2 = "execution"
Output: 5

Input: word1 = "", word2 = "a"
Output: 1

Maslahatlar

1. Bu ikki satrni solishtiruvchi klassik 2D dinamik dasturlash — dp[i][j] ni "word1 ning birinchi i ta va word2 ning birinchi j ta belgisini bir-biriga aylantirish uchun kerak bo'ladigan minimal amallar soni" sifatida belgilang.
2. Agar so'nggi belgilar teng bo'lsa (word1[i-1]==word2[j-1]), dp[i][j] = dp[i-1][j-1]. Aks holda dp[i][j] = 1 + min(dp[i-1][j-1] — almashtirish, dp[i-1][j] — o'chirish, dp[i][j-1] — qo'shish). Bazaviy qator/ustunlarni dp[i][0]=i va dp[0][j]=j deb sozlang.