Here is the bottom up solution as described in the article. It’s worth mentioning that for the case where word[i] != word[j] and we must perform 1 of 3 actions we must pick the minimum of the previous 3 possible actions taken and add 1 (the current action).
def min_distance(word1: str, word2: str) → int:
dp = [[0] * (len(word1)+1) for _ in range(len(word2) + 1)]
for r in range(len(dp)):
dp[r][0] = r
for c in range(len(dp[0])):
dp[0][c] = c
for i in range(1, len(dp)):
for j in range(1, len(dp[0])):
if word1[j-1] != word2[i-1]:
dp[i][j] = 1 + min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])
else:
dp[i][j] = dp[i-1][j-1]
return dp[-1][-1]
def min_distance(word1: str, word2: str) -> int:
# WRITE YOUR BRILLIANT CODE HERE
dp = [[float("inf")] * (len(word2)+1) for i in range(len(word1)+1)]
for i in range(len(word2)+1):
dp[len(word1)][i] = len(word2)-i
for j in range(len(word1)+1):
dp[j][len(word2)] = len(word1) -j
for i in range(len(word1)-1, -1, -1):
for j in range(len(word2)-1, -1, -1):
if word1[i] == word2[j]:
dp[i][j] = dp[i+1][j+1]
else:
dp[i][j] = 1 + min(dp[i+1][j], dp[i][j+1], dp[i+1][j+1])
return dp[0][0]
if __name__ == '__main__':
word1 = input()
word2 = input()
res = min_distance(word1, word2)
print(res)
Top down solution
int dfs(string & w1, string & w2, int m, int n, vector<vector<int>> & dp) {
if(m <= 0) {
return n; // remaining w2 add cost
}
if(n <= 0) {
return m; // remaining w1 add cost
}
if(dp[m][n]) return dp[m][n];
int cost = w1[m-1] == w2[n-1] ? 0 : 1;
int minLcs = min(
min(dfs(w1, w2, m-1, n, dp) + 1, dfs(w1, w2, m, n-1, dp) + 1),
cost + dfs(w1, w2, m-1, n-1, dp)
);
return dp[m][n] = minLcs;
}
Bottom up solution:
function minDistance(word1, word2) {
const n = word1.length;
const m = word2.length;
const dp = Array.from({
length: n + 1
}, () => Array(m + 1).fill(Infinity));
for (let i = 0; i <= n; i++) {
for (let j = 0; j <= m; j++) {
if ([i, j].includes(0)) {
dp[i][j] = i || j;
continue;
}
const cost = word1[i - 1] === word2[j - 1] ? 0 : 1;
dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + cost);
}
}
return dp[n][m];
}
function minDistance(word1, word2) {
const n = word1.length;
const m = word2.length;
const dp = Array.from({
length: n + 1
}, () => Array(m + 1).fill(Infinity));
for (let i = 0; i <= n; i++) {
for (let j = 0; j <= m; j++) {
if ([i, j].includes(0)) {
dp[i][j] = i || j;
continue;
}
const cost = word1[i - 1] === word2[j - 1] ? 0 : 1;
dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + cost);
}
}
return dp[n][m];
}
def min_distance(word1: str, word2: str) → int:
def dfs(i, j, memo={}):
midx = (i,j) # easier to cache dict of tuple than dict of dict
if midx in memo:
return memo[midx]
if i == len(word1) or j == len(word2): # reach end of 1 word but not other
return max(len(word1)-i, len(word2)-j)
ans = 0
if word1[i] == word2[j]:
ans = dfs(i+1,j+1,memo) # they match so move on to next char
else:
# no match so delete 1 char in first or second or replace both
# take the min num of moves and add 1 more move
ans = min(dfs(i+1,j,memo), dfs(i,j+1,memo), dfs(i+1,j+1,memo)) + 1
memo[midx] = ans
return ans
return dfs(0,0)
- match
word1[i]to blank (deleteword2[j]) - match
word2[j]to blank (addword1[i])
There two descriptions are miss-leading. Really hard to build intuition based on them.
word2 cannot be edited, how to “delete word2[j]”
add word1[i] to match what? the precondition how we reach this step is that word1[i] != word2[j].
Not sure how “add word1[i]” help matching.
Should them be
- Insert word2[j] to i position of word1 to match and then move index to j-1 on word2 and Leave word1’s index unchanged since word1[i] is not used to match yet
- Delete word1[i], move index to i-1 on word1 and Leave word2’s index unchanged since on matching found yet
Thank you so much for your comment, this helped me understand the solution much more faster.
I also agree that the solution description should be reworded to something similar.