Day56(583, 72)
583. Delete Operation for Two Strings
Given two strings word1
and word2
, return the minimum number of steps required to make word1
and word2
the same.
In one step, you can delete exactly one character in either string.
Example 1:
Input: word1 = “sea”, word2 = “eat”
Output: 2
Explanation: You need one step to make “sea” to “ea” and another step to make “eat” to “ea”.
Example 2:
Input: word1 = “leetcode”, word2 = “etco”
Output: 4
class Solution { public int minDistance(String word1, String word2) { int len1 = word1.length(); int len2 = word2.length(); int[][] dp = new int[len1 + 1][len2 + 1]; for (int i = 1; i <= len1; i++) { for (int j = 1; j <= len2; j++) { if (word1.charAt(i - 1) == word2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return len1 + len2 - dp[len1][len2] * 2; }
}
72. 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’)
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 i = 1; i <= m; i++) { dp[i][0] = i; } for (int j = 1; j <= n; j++) { dp[0][j] = j; } 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(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1; } } } return dp[m][n]; }
}