72. Edit Distance
Hard
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
- Insert a character
- Delete a character
- Replace a character
Example 1:
Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e')
Example 2:
Input: word1 = "intention", word2 = "execution" Output: 5 Explanation: intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u')
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | //C++: 28ms method1 space O(m*n); class Solution { public: int minDistance(string word1, string word2) { int n1 = word1.size(); int n2 = word2.size(); vector<vector<int>> dp(n1+1, vector<int>(n2+1)); for(int j=0; j<=n2; ++j) dp[0][j] = j; for(int i=0; i<=n1; ++i) dp[i][0] = i; for(int i=1; i<=n1; ++i){ for(int j=1; j<=n2; ++j){ if(word1[i-1]==word2[j-1]){ dp[i][j] = dp[i-1][j-1]; }else{ dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))+1; } } } return dp[n1][n2]; } }; //C++: 20ms method2 space O(min(m, n)); class Solution { public: int minDistance(string word1, string word2) { int n1 = word1.size(), n2 = word2.size(); if(n2>n1) return minDistance(word2, word1); vector<int> row_old(n2+1, 0), row(n2+1, 0); for(int j=0; j<=n2; ++j) row_old[j] = j; for(int i=1; i<=n1; ++i){ row[0] = i; for(int j=1; j<=n2; ++j){ if(word1[i-1]==word2[j-1]){ row[j] = row_old[j-1]; }else{ row[j] = 1+min(min(row_old[j], row[j-1]), row_old[j-1]); } } row_old = row; } return row[n2]; } }; //Java class Solution { public int minDistance(String word1, String word2) { int m = word1.length(); int n = word2.length(); int[][] dp = new int[m+1][n+1]; for(int j=1; j<=n; ++j) dp[0][j] = j; for(int i=1; i<=m; ++i) dp[i][0] = i; for(int i=1; i<=m; ++i){ for(int j=1; j<=n; ++j){ if(word1.charAt(i-1)==word2.charAt(j-1)){ dp[i][j] = dp[i-1][j-1]; }else{ dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]))+1; } } } return dp[m][n]; } } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | //Java class Solution { public int minDistance(String word1, String word2) { int m = word1.length(); int n = word2.length(); int[][] dp = new int[m+1][n+1]; for(int j=1; j<=n; ++j) dp[0][j] = j; for(int i=1; i<=m; ++i) dp[i][0] = i; for(int i=1; i<=m; ++i){ for(int j=1; j<=n; ++j){ if(word1.charAt(i-1)==word2.charAt(j-1)){ dp[i][j] = dp[i-1][j-1]; }else{ dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]))+1; } } } return dp[m][n]; } } |
No comments:
Post a Comment