Edit Distance
Desicription
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
 class Solution { public: int minDistance(string word1, string word2) { int n = word1.size(); int m = word2.size(); vector<vector<int>> dp(n+1, vector<int>(m+1, 0)); for(int i = 1; i <= n; i++) dp[i][0] = i; for(int i = 1; i <= m; i++) dp[0][i] = i; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(word1[i1] == word2[j1]) dp[i][j] = dp[i1][j1]; else dp[i][j] = min(dp[i1][j1] + 1, min(dp[i1][j] + 1, dp[i][j1] + 1)); } } return dp[n][m]; } };
