1. //给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。 
  2. //
  3. // 
  4. //
  5. // 示例： 
  6. //
  7. // 输入: "sea", "eat"
  8. //输出: 2
  9. //解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
  10. // 
  11. //
  12. // 
  13. //
  14. // 提示： 
  15. //
  16. // 
  17. // 给定单词的长度不超过500。 
  18. // 给定单词中的字符只含有小写字母。 
  19. // 
  20. // Related Topics 字符串 
  21. // 👍 158 👎 0

题目的隐藏含义是：寻找两个字符串的最长公共子序列。
即，字符在字符串中的相对顺序一定，但不必连续。

删除最少的字符使两个单词相等，得到的删除后的结果就是最长子序列。

动态规划

以两个字符串的长度，定义一个数组。dp[i][j]代表word1的前i位和word2的前j位中包含的最长公共子序列长度。
如果word1[i] == word2[j]，说明在两个字符串的i，j位置出现了相同的字符，这种情况直接可以选取前面的数值+1。
如果word1[i] != word2[j]，说明i，j位置的字符不想等，此时的最长子序列长度是i，j位置前的长度，因为没有找到相同字符，所以长度跟前面长度的最长长度相等。


class Solution {

    public int minDistance(String word1, String word2) {
        // 0位置代表两个空字符串的比较
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];

        // 从1开始，因为空字符串和任何字符串的公共子序列长度都是0
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                // i指向1的时候，实际上选择的字符是第0个，因此需要-1
                if (word1.charAt(i - 1) == word2.charAt(j - 1)){
                    // 如果选择的两个字符相等，直接取这两个位置前面的值再加1即可
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
                    // 如果选择的两个字符不想等，要么不选i位置的字符，要么不选j位置的字符
                    // 选之前最长的公共子序列长度
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        // dp[word1.length()][word2.length()]就是最长公共子序列的长度，要删除的字符就是总字符减去这个值*2
        return word1.length() + word2.length() - 2 * dp[word1.length()][word2.length()];
    }
}