source: https://leetcode.com/problems/edit-distance/
Edit Distance
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.
You have the following three 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’)
Constraints:
- 0 <= word1.length, word2.length <= 500
- word1 and word2 consist of lowercase English letters.
|
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 |
class Solution { public int minDistance(String word1, String word2) { char[] c1 = word1.toCharArray(); char[] c2 = word2.toCharArray(); int[][] memo = new int[c1.length+1][c2.length+1]; for(int[] m: memo) Arrays.fill(m, -1); return dfs(c1, c2, 0, 0, memo); } private int dfs(char[] c1, char[] c2, int index1, int index2, int[][] memo){ if(index1>=c1.length && index2>=c2.length){ return 0; } //remaining operations to make two strings equal if(index1>=c1.length){ return c2.length - index2; } if(index2>=c2.length){ return c1.length-index1; } if(memo[index1][index2]!=-1){ return memo[index1][index2]; } int min = Integer.MAX_VALUE; //if both the characters are same if(c1[index1] == c2[index2]){ min = Math.min(min, dfs(c1, c2, index1+1, index2+1, memo)); } else { //we have two choices either we can insert that character in word1 min = Math.min(min, 1+dfs(c1, c2, index1, index2+1, memo)); //or we can remove that charcater from word1 min = Math.min(min, 1+dfs(c1, c2, index1+1, index2, memo)); //or we can replace the charcater min = Math.min(min, 1+dfs(c1, c2, index1+1, index2+1, memo)); } memo[index1][index2] = min; return min; } } |