题目

image.png

思路

  • 思路一：暴力递归解决，由于对于每个字符不相等情况下我们有三种选择，1、删除该字符，2、替换该字符、3插入新字符，因此我们直接暴力尝试这三种可能性选择其中最小的
  • 思路二：备忘录，由于暴力递归会超时，因此我们用容器将已经尝试过的结果记录下来，再进行选择。

  • 思路三：动态规划，就是将递归变为循环，将递归的结果变成用dp数组记录下来，而dp数组的转移条件就是暴力中所提到的三个条件，关键在于如何定义dp数组，定义dp[i][j]表示word1的前i个字符到word2的前j个字符最短步骤 | 0 | 1 | 2 | | —- | —- | —- | | 1 | a | b | | 2 | c | d | | 3 | | |

  • 思路四：优化dp数组的动态规划，在动态规划中，我们需要用到二维dp数组，但是从遍历来看，每次只用到了dp[i-1]p[j-1]和dp[i][j-1]和dp[i-1][j]，因此我们需要记录一行结果和以及更新后结果，更新后的数据覆盖之前的结果，但是还要用到因此需要用prev记录覆盖之前的结果，比如计算a需要用到0、1、1，假设得到结果为1，然后放到数组对应的位置，继续计算b，需要用到1、a、2，但是由于a已经覆盖了1，所以需要额外变量记录1的结果

  • prev = 1，计算b的值，下列表格显示的是第二行计算完a的dp数组结果 | 1 | 1 | 2 | | —- | —- | —- |

代码

  1.     //1、暴力递归超时
  2.     public int minDistance(String word1, String word2) {
  3.         return recur(word1.toCharArray(), 0, word2.toCharArray(), 0);
  4.     }
  6.     public int recur(char[] word1, int i, char[] word2, int j) {
  7.         if (i >= word1.length || j >= word2.length) return  word1.length + word2.length - i - j;
  8.         if (word1[i] == word2[j]) return recur(word1, i + 1, word2, j + 1);
  9.         return 1 + Math.min(
  10.             //删除、替换、插入
  11.             Math.min(recur(word1, i + 1, word2, j), recur(word1, i + 1, word2, j + 1)), 
  12.             recur(word1, i, word2, j + 1));
  13.     }
  15.     //2.备忘录
  16.     HashMap<String, Integer> map = new HashMap<>();
  17.     public int minDistance(String word1, String word2) {
  18.         return recur(word1.toCharArray(), 0, word2.toCharArray(), 0);
  19.     }
  21.     public int recur(char[] word1, int i, char[] word2, int j) {
  22.         String key = i + "-" + j;
  23.         if (map.containsKey(key)) return map.get(key);
  24.         if (i >= word1.length || j >= word2.length) return  word1.length + word2.length - i - j;
  25.         int res = 0;
  26.         if (word1[i] == word2[j]) res = recur(word1, i + 1, word2, j + 1);
  27.         else res = 1 + Math.min(
  28.             Math.min(recur(word1, i + 1, word2, j), recur(word1, i + 1, word2, j + 1)), 
  29.             recur(word1, i, word2, j + 1));
  30.         map.put(key, res);
  31.         return res;
  32.     }
  34.     //3. 动态规划
  35.     public int minDistance(String word1, String word2) {
  36.         int len1 = word1.length();
  37.         int len2 = word2.length();
  38.         //dp[i][j]表示word1的i到word2的j的单词转换所需最小步骤
  39.         int[][] dp = new int[len1 + 1][len2 + 1];
  40.         for (int i = 0; i <= len1; i++) {
  41.             dp[i][0] = i;
  42.         }
  43.         for (int j = 0; j <= len2; j++) {
  44.             dp[0][j] = j;
  45.         }
  46.         for (int i = 1; i <= len1; i++) {
  47.             for (int j = 1; j <= len2; j++) {
  48.                 if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
  49.                     dp[i][j] = dp[i - 1][j - 1];
  50.                 } else {
  51.                     //插入、删除，替换
  52.                     dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);
  53.                 }
  54.             }
  55.         }
  56.         return dp[len1][len2];
  57.     }
  59.     //4. 优化dp数组的动态规划
  60.     public int minDistance(String word1, String word2) {
  61.         int len1 = word1.length();
  62.         int len2 = word2.length();
  63.         //dp[j]表示到word2的j的单词转换所需最小步骤
  64.         int[] dp = new int[len2 + 1];
  65.         for (int j = 0; j <= len2; j++) {
  66.             dp[j] = j;
  67.         }
  68.         for (int i = 1; i <= len1; i++) {
  69.             int prev = i - 1;
  70.             dp[0] = i;
  71.             for (int j = 1; j <= len2; j++) {
  72.                 int t = dp[j];
  73.                 if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
  74.                     dp[j] = prev;
  75.                 } else {
  76.                     //插入、删除，替换
  77.                     dp[j] = 1 + Math.min(Math.min(dp[j], dp[j - 1]), prev);
  78.                 }
  79.                 prev = t;
  80.             }
  81.         }
  82.         return dp[len2];
  83.     }

编辑距离