# Edit Distance - Dynamic Programming / Two Sequences

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 = [ * (len(word1)+1) for _ in range(len(word2) + 1)]

for r in range(len(dp)):
dp[r] = r

for c in range(len(dp)):
dp[c] = c

for i in range(1, len(dp)):
for j in range(1, len(dp)):

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

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)
``````