lc 72 edit distance

DP-LC 72 Edit Distance

dp[i][j]: the minimum steps to convert word1[0…i] to word2[0…j]
i : [0… word1.length()] the length of word1, i == 0 => word1 is an empty string
j: [0…word2.length()] the length of word2

dynamic programming idea:
Assume we know the previous result dp[i-1]
j-1 to word20… j-2)
if word1[i-1] == word2[j-1], that means we don’t need to do conversion, dp[i][j] = dp[i-1][j-1].
else
there are three options to convert the word1[i-1] to word2[j-1]
replace: dp[i][j] = dp[i-1][j-1] + 1;
delete: word1[0… i-2] == word2[0… j-1] dp[i][j] = dp[i-1][j] + 1;
insert: word1[0…i-1] == word2[0… j-2] dp[i][j] = dp[i][j-1] + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int (string word1, string word2) {
int m = (int)word1.length();
int n = (int)word2.length();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

for(int i = 1;i <= m; i++)
dp[i][0] = i;
for(int j = 1; j <= n; j++)
dp[0][j] = j;

for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(word1[i-1] == word2[j-1])
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = min(min(dp[i-1][j-1]+1, dp[i-1][j]+1), dp[i][j-1]+1);

}
}
return dp[m][n];
}