583. 两个字符串的删除操作 - 已题解语言：Java, C#, Python, C++, JavaScript, Go, Ruby

力扣题解最佳实践 > 动态规划 > 583. 两个字符串的删除操作 > 已用 Java, C#, Python, C++, JavaScript, Go, Ruby 语言实现 > 贡献代码或转发

力扣链接：583. 两个字符串的删除操作，难度：中等。

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步可以删除任意一个字符串中的一个字符。

示例 1:

输入: word1 = "sea", word2 = "eat"

输出: 2

解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

示例 2:

输入: word1 = "leetcode", word2 = "etco"

输出: 4

约束:

1 <= word1.length, word2.length <= 500
word1 和 word2 只包含小写英文字母

思路
上一题 下一题

这是一道比较两个字符串的问题。在多次做过类似的题目之后，我们会形成使用二维数组动态规划的直觉。

“动态规划”的模式

“动态规划”分为五步

确定数组dp的每个值代表的含义。
初始化数组dp的值。
根据一个示例，“按顺序”填入dp网格数据。
根据dp网格数据，推导出“递推公式”。
写出程序，并打印dp数组，不合预期就调整。

细说这五步

确定数组dp的每个值代表的含义。
- 先确定dp是一维数组还是二维数组。“一维滚动数组”意味着每次迭代时都会覆盖数组的值。大多时候，用“一维滚动数组”代替“二维数组”可以简化代码；但有些题目，比如要操作“两个对等数组”，为了理解方便，还是使用“二维数组”。
- 尝试使用问题所求的返回值的含义作为 dp[i]（一维）或dp[i][j]（二维）的含义，约60%的概率能行。如果不行，再尝试其他含义。
- 设计上尽量考虑保存更丰富的信息，重复信息只在某个dp[i]中保存一次就够了。
- 使用简化的含义。如果用布尔值可以解决问题，就不要用数值。
初始化数组dp的值。dp的值涉及两个层面：
1. dp的长度。通常是：条件数组长度加1或条件数组长度。
2. dp[i]或dp[i][j]的值。dp[0]或dp[0][0]有时需要特殊处理。
根据一个示例，“按顺序”填入dp网格数据。
- “递推公式”是“动态规划”算法的核心。但“递推公式”是隐晦的，想得到它，就需要制表，用数据启发自己。
- 如果原示例不够好，需要自己重新设计一个。
- 根据示例，填入dp网格数据，需要“按顺序”填，这是很重要的，因为它决定了代码的遍历顺序。
- 大多时候，从左到右，从上到下。但有时需要从右向左、由下而上、从中间向右（或左），如“回文串”问题。有时，还需要一行遍历两次，先正向，再反向。
- 当顺序决定对了，起点就决定好了，从起点出发，“按顺序”填写dp网格数据，这也是在模拟程序处理的过程。
- 在此过程中，您将获得写出“递推公式”的灵感。如果您已经能推导出公式，不需要填完网格。
根据dp网格数据，推导出“递推公式”。
- 有三个特别的位置需要注意： dp[i - 1][j - 1]、dp[i - 1][j]和dp[i][j - 1]，当前的 dp[i][j]往往取决于它们。
- 操作“两个对等数组”时，因为对称性，我们可能需要同时使用dp[i - 1][j]和dp[i][j - 1]。
写出程序，并打印dp数组，不合预期就调整。
- 重点分析那些不合预期的数值。

读完了上面的内容，是不是感觉“动态规划”也没有那么难了？试着解出这道题吧。🤗

步骤

“动态规划”的常用步骤

这五个步骤是解决动态规划问题的一个模式。

确定dp[i][j]的含义
- 因为有两个字符串，所以我们可以使用二维数组作为默认选项。
- 首先尝试使用问题的return值作为dp[i][j]的值来确定dp[i][j]的含义。如果不行，再尝试其他方法。
- dp[i][j]表示使word1的前i个字母和word2的前j个字母相同所需的最少步数。
- dp[i][j]是一个整数。
确定 dp 数组的初值
- 举例说明：
```
初始化后，'dp' 数组为：
# e a t
# 0 1 2 3 # dp[0]
# s 1 0 0 0
# e 2 0 0 0
# a 3 0 0 0
```
- dp[0][j] = j，因为 dp[0] 表示空字符串，步数就是要删除的字符数。
- dp[i][0] = i，理由和上一行一样，只是从垂直方向看。
确定 dp 数组的递归公式
- 尝试完成网格。在这个过程中，你会得到推导公式的灵感。
```
1. word1 = "s", word2 = "eat"
# e a t
# 0 1 2 3
# s 1 2 3 4 # dp[1]
```
```
2. word1 = "se", word2 = "eat"
# e a t
# 0 1 2 3
# s 1 2 3 4
# e 2 1 2 3
```
```
3. word1 = "sea", word2 = "eat"
# e a t
# 0 1 2 3
# s 1 2 3 4
# e 2 1 2 3
# a 3 2 1 2
```
- 在分析示例 dp 网格时，请记住有三个要点需要特别注意：dp[i - 1][j - 1]、dp[i - 1][j] 和 dp[i][j - 1]。当前的 dp[i][j] 通常取决于它们。
- 如果问题反过来也是正确的（交换 word1 和 word2），并且我们需要使用 dp[i - 1][j] 或 dp[i][j - 1]，那么我们可能需要同时使用它们。
- 我们可以推导出 递归公式：
```
if word1[i - 1] == word2[j - 1]
  dp[i][j] = dp[i - 1][j - 1]
else
  dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1
end
```
确定 dp 数组的遍历顺序
- dp[i][j] 依赖于 dp[i - 1][j - 1]、dp[i - 1][j] 和 dp[i][j - 1]，所以我们应该从上到下，然后从左到右遍历 dp 数组。
检查 dp 数组的值
- 打印 dp 以查看它是否符合预期。

复杂度

时间复杂度

O(N * M)

空间复杂度

O(N * M)

Java #

class Solution {
    public int minDistance(String word1, String word2) {
        var dp = new int[word1.length() + 1][word2.length() + 1];
        for (var i = 0; i < dp.length; i++) {
            dp[i][0] = i;
        }
        for (var j = 0; j < dp[0].length; j++) {
            dp[0][j] = j;
        }

        for (var i = 1; i < dp.length; i++) {
            for (var j = 1; j < dp[0].length; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }

        return dp[dp.length - 1][dp[0].length - 1];
    }
}

C# #

public class Solution
{
    public int MinDistance(string word1, string word2)
    {
        var dp = new int[word1.Length + 1, word2.Length + 1];

        for (var i = 0; i < dp.GetLength(0); i++)
            dp[i, 0] = i;

        for (var j = 0; j < dp.GetLength(1); j++)
            dp[0, j] = j;

        for (var i = 1; i < dp.GetLength(0); i++)
        {
            for (var j = 1; j < dp.GetLength(1); j++)
            {
                if (word1[i - 1] == word2[j - 1])
                {
                    dp[i, j] = dp[i - 1, j - 1];
                }
                else
                {
                    dp[i, j] = Math.Min(dp[i - 1, j], dp[i, j - 1]) + 1;
                }
            }
        }

        return dp[dp.GetUpperBound(0), dp.GetUpperBound(1)];
    }
}

Python #

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0] * (len(word2) + 1) for _ in range(len(word1) + 1)]
        for i in range(len(dp)):
            dp[i][0] = i
        for j in range(len(dp[0])):
            dp[0][j] = j

        for i in range(1, len(dp)):
            for j in range(1, len(dp[0])):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1

        return dp[-1][-1]

C++ #

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
        for (auto i = 0; i < dp.size(); i++) {
            dp[i][0] = i;
        }
        for (auto j = 0; j < dp[0].size(); j++) {
            dp[0][j] = j;
        }

        for (auto i = 1; i < dp.size(); i++) {
            for (auto j = 1; j < dp[0].size(); j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }

        return dp[dp.size() - 1][dp[0].size() - 1];
    }
};

JavaScript #

var minDistance = function (word1, word2) {
  const dp = Array(word1.length + 1).fill().map(
    () => Array(word2.length + 1).fill(0)
  )
  dp.forEach((_, i) => { dp[i][0] = i })
  dp[0].forEach((_, j) => { dp[0][j] = j })

  for (let i = 1; i < dp.length; i++) {
    for (let j = 1; j < dp[0].length; j++) {
      if (word1[i - 1] == word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1]
      } else {
        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1
      }
    }
  }

  return dp.at(-1).at(-1)
};

Go #

func minDistance(word1 string, word2 string) int {
    dp := make([][]int, len(word1) + 1)
    for i := range dp {
        dp[i] = make([]int, len(word2) + 1)
        dp[i][0] = i
    }
    for j := range dp[0] {
        dp[0][j] = j
    }

    for i := 1; i < len(dp); i++ {
        for j := 1; j < len(dp[0]); j++ {
            if word1[i - 1] == word2[j - 1] {
                dp[i][j] = dp[i - 1][j - 1]
            } else {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1
            }
        }
    }

    return dp[len(dp) - 1][len(dp[0]) - 1]
}

Ruby #

def min_distance(word1, word2)
  dp = Array.new(word1.size + 1) do
    Array.new(word2.size + 1, 0)
  end
  dp.each_with_index do |_, i|
    dp[i][0] = i
  end
  dp[0].each_with_index do |_, j|
    dp[0][j] = j
  end

  (1...dp.size).each do |i|
    (1...dp[0].size).each do |j|
      dp[i][j] =
        if word1[i - 1] == word2[j - 1]
          dp[i - 1][j - 1]
        else
          [ dp[i - 1][j], dp[i][j - 1] ].min + 1
        end
    end
  end

  dp[-1][-1]
end

其它语言

欢迎贡献代码到我们的 GitHub 仓库，非常感谢！本题解位置在 583. 两个字符串的删除操作。

上一题下一题

游客

全部题解

Welcome !

力扣题解最佳实践 > 动态规划 > 583. 两个字符串的删除操作 > 已用 Java, C#, Python, C++, JavaScript, Go, Ruby 语言实现 > 贡献代码 或 转发