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最长相同子序列长度
part2: 算出最小步数

part1:
dp[i][j]表示:word1的前i个字符 和 word2的前j个字符 组成的 两个单词的最长公共子序列的长度。

递推式:
如果当前的两个字符相等，那么dp[i][j] = dp[i-1][j-1] + 1
否则，则错位相比，比如就拿题目中的例子来说，"sea"和"eat"，当我们比较第一个字符，发现's'和'e'不相等，下一步就要错位比较啊，比较sea中第一个's'和eat中的'a'，sea中的'e'跟eat中的第一个'e'相比，这样我们的dp[i][j]就要取dp[i-1][j]跟dp[i][j-1]中的较大值了。

part2:
得到最大共同子序列的长度，就能直接算出最小步数了。参见代码如下：

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;
    }
}