一、题目

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

点击查看原题
难度级别： 中等

二、思路

1）动态规划

该题可以将问题转化为寻找两个字符串中相同的最长字符序列
让dp[i][j]为word2[0, i-1]和word2[0, j-1]相同最长字符序列长度，那么可以得到状态转移方程：
583. 两个字符串的删除操作-每日一题 - 图1
由于状态只依赖于当前行和i-1行状态，可以优化为一维dp数组

三、代码

1）动态规划

  1. class Solution {
  2.     public int minDistance(String word1, String word2) {
  3.         int[][] dp = new int[word1.length() + 1][word2.length() + 1];
  4.         for (int i = 0; i < word1.length(); i++) {
  5.             for (int j = 0; j < word2.length(); j++) {
  6.                 if (word1.charAt(i) == word2.charAt(j)) {
  7.                     dp[i+1][j+1] = dp[i][j] + 1;
  8.                 } else {
  9.                     dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j]);
  10.                 }
  11.             }
  12.         }
  13.         return word1.length() + word2.length() - 2*dp[word1.length()][word2.length()];
  14.     }
  15. }

两个字符串长度分别为n和m，时间复杂度为O(n*m)，空间复杂度为O(n*m)
优化空间复杂度后为：

  1. class Solution {
  2.     public int minDistance(String word1, String word2) {
  3.         int[] dp = new int[word2.length() + 1];
  4.         for (int i = 0; i < word1.length(); i++) {
  5.             int cur = 0;    // 记录上一个，如果当前是j+1，那也就是dp[j]元素
  6.             for (int j = 0; j < word2.length(); j++) {
  7.                 int leftTop = cur;
  8.                 cur = dp[j + 1];
  9.                 if (word1.charAt(i) == word2.charAt(j)) {
  10.                     dp[j+1] = leftTop + 1;
  11.                 } else {
  12.                     dp[j+1] = Math.max(dp[j+1], dp[j]);
  13.                 }
  14.             }
  15.         }
  16.         return word1.length() + word2.length() - 2*dp[word2.length()];
  17.     }
  18. }
  1. 两个字符串长度分别为`n`和`m`，时间复杂度为`O(n*m)`，空间复杂度为`O(m)`