class Solution:
def minDistance(self, word1: str, word2: str) -> int:
if not word1 and not word2:
return 0
if word1 == word2:
return 0
dp = []
for i in range(len(word1)+1):
a = []
for j in range(len(word2)+1):
a.append(0)
dp.append(a)
for i in range(len(word1)+1):
dp[i][0] = i
for i in range(len(word2) +1):
dp[0][i] = i
for i in range(1, len(word1)+1, 1):
for j in range(1, len(word2)+1, 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
return dp[-1][-1]
80A - Panoramix's Prediction | 1354B - Ternary String |
122B - Lucky Substring | 266B - Queue at the School |
1490A - Dense Array | 1650B - DIV + MOD |
1549B - Gregor and the Pawn Game | 553A - Kyoya and Colored Balls |
1364A - XXXXX | 1499B - Binary Removals |
1569C - Jury Meeting | 108A - Palindromic Times |
46A - Ball Game | 114A - Cifera |
776A - A Serial Killer | 25B - Phone numbers |
1633C - Kill the Monster | 1611A - Make Even |
1030B - Vasya and Cornfield | 1631A - Min Max Swap |
1296B - Food Buying | 133A - HQ9+ |
1650D - Twist the Permutation | 1209A - Paint the Numbers |
1234A - Equalize Prices Again | 1613A - Long Comparison |
1624B - Make AP | 660B - Seating On Bus |
405A - Gravity Flip | 499B - Lecture |