Edit Distance - Dynamic Programming / Two Sequences

Problems
1

https://algo.monster/problems/edit_distance

4

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]
5 
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)
7

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;
}
8

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];
}

9 
 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];
}
10

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)
12
  1. match word1[i] to blank (delete word2[j])
  2. match word2[j] to blank (add word1[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

  1. 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
  2. Delete word1[i], move index to i-1 on word1 and Leave word2’s index unchanged since on matching found yet
1 Like
13

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.