Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.
Example 1:
Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
Note:
The length of given words won't exceed 500.
Characters in given words can only be lower-case letters.
Solution：
思路：
part1: 先求Longest Common Subsequence最長(zhǎng)相同子序列長(zhǎng)度
part2: 算出最小步數(shù)
part1:
dp[i][j]表示:word1的前i個(gè)字符 和 word2的前j個(gè)字符 組成的 兩個(gè)單詞的最長(zhǎng)公共子序列的長(zhǎng)度棋弥。
遞推式:
如果當(dāng)前的兩個(gè)字符相等框沟，那么dp[i][j] = dp[i-1][j-1] + 1
否則曲横，則錯(cuò)位相比桨啃，比如就拿題目中的例子來(lái)說(shuō)睦刃，"sea"和"eat"砚嘴，當(dāng)我們比較第一個(gè)字符，發(fā)現(xiàn)'s'和'e'不相等涩拙，下一步就要錯(cuò)位比較啊际长，比較sea中第一個(gè)'s'和eat中的'a'，sea中的'e'跟eat中的第一個(gè)'e'相比兴泥，這樣我們的dp[i][j]就要取dp[i-1][j]跟dp[i][j-1]中的較大值了工育。
part2:
得到最大共同子序列的長(zhǎng)度，就能直接算出最小步數(shù)了搓彻。參見(jiàn)代碼如下：
Time Complexity: O(n1n2) Space Complexity: O(n1n2)
Solution Code：
class Solution {
public int minDistance(String word1, String word2) {
int n1 = word1.length();
int n2 = word2.length();
int dp[][] = new int[n1 + 1][n2 + 1];
for(int i = 0; i <= n1; i++) {
for(int j = 0; j <= n2; j++) {
if(i == 0 || j == 0) dp[i][j] = 0;
else dp[i][j] = (word1.charAt(i - 1) == word2.charAt(j - 1)) ? dp[i - 1][j - 1] + 1
: Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
int longest_comm_length = dp[n1][n2];
return n1 - longest_comm_length + n2 - longest_comm_length;
}
}
