Edit Distance
Given two strings s and t. Return the minimum number of operations required to convert s to t.
The possible operations are permitted:
- Insert a character at any position of the string.
- Remove any character from the string.
- Replace any character from the string with any other character.
- Time : O(nm)
- Space : O(nm)
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 editDistance(string s, string t) { int n = s.length(), m = t.length();
vector<vector<int>> dp(n + 1, vector<int>(m + 1)); for(int i = 0; i < n; i++) dp[0][i] = i; for(int j = 0; j < m; j++) dp[j][0] = j; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1]; else dp[i][j] = 1 + min({ dp[i-1][j], dp[i-1][j-1], dp[i][j-1] }); } }
return dp[n][m]; } };
|