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 |
int (string word1, string word2) { |
近期评论