LeetCode 583 - Delete Operation for Two Strings

http://blog.csdn.net/u014688145/article/details/71948763

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.

最小编辑距离的简单版本，直接用DP解决即可。

思路：

dp[i][j]：表示word1[0,i)和word2[0,j)的最小编辑距离。

两种情况：

if word1[i] == word2[j]; dp[i+1][j+1] = dp[i][j];
if word2[i] != word2[j]; dp[i+1][j+1] = 1 + max{dp[i][j+1],dp[i+1][j]}

public int minDistance(String word1, String word2) { int n = word1.length(); int m = word2.length(); int[][] dp = new int[n+1][m+1]; for (int i = 0; i < n; i++){ Arrays.fill(dp[i], 1<<30); } dp[0][0] = 0; for (int i = 0; i < n; i++){ dp[i+1][0] = i+1; } for (int j = 0; j < m; j++){ dp[0][j+1] = j+1; } for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++){ if (word1.charAt(i) == word2.charAt(j)){ dp[i+1][j+1] = dp[i][j]; }else{ dp[i+1][j+1] = Math.min(dp[i][j+1]+1, Math.min(dp[i+1][j]+1, dp[i][j]+2)); } } } return dp[n][m]; }

可优化的地方：

• dp初始化为INF可以去除，只要把min中的+1提取出来即可。
• dp[0][j]和dp[i][0]的更新可以合并到双重循环中。

public int minDistance(String word1, String word2) { int n = word1.length(); int m = word2.length(); int[][] dp = new int[n+1][m+1]; for (int i = 0; i <= n; i++){ for (int j = 0; j <= m; j++){ if (i == 0 || j == 0){ dp[i][j] = i + j; continue; } if (word1.charAt(i-1) == word2.charAt(j-1)){ dp[i][j] = dp[i-1][j-1]; }else{ dp[i][j] = 1 + Math.min(dp[i-1][j], dp[i][j-1]); } } } return dp[n][m]; }


http://bookshadow.com/weblog/2017/05/15/leetcode-delete-operation-for-two-strings/

最长公共子序列（Longest Common Subsequence）

求word1和word2的LCS

ans = len(word1) + len(word2) - 2 * len(LCS)