LeetCode: 583. Delete Operation for Two Strings

发表于 | 分类于

题目描述

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:

1
2
3
Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

动态规划题，和之前找两个词之间的距离那道题目很相近。令dp[i][j]为第一个字母从0到i和第二个字母从0到j的需要删除的最少次数。状态转移方程为:

就是当对于word1的索引i，word2的索引j来说，如果word1[i] == word2[j]的话，dp[i][j]就是dp[i-1][j-1]，因为此时只需要根据dp[i-1][j-1]的方式就可以处理dp[i][j]，否则，则只需要判断dp[i-1][j]和dp[i][j-1]哪个小就可以了，因为只需要对word1或word2删除最后一个元素就可以回到前面的两个状态。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int minDistance(string word1, string word2) {
        if (word1.length() == 0)
            return word2.length();
        if (word2.length() == 0)
            return word1.length();

        vector<vector<int>> dp(word1.size()+1, vector<int> (word2.size()+1));
        for (int i = 0; i < dp.size(); i++) {
            dp[i][0] = i;
        }

        for (int i = 0; i < dp[0].size(); i++) {
            dp[0][i] = i;
        }

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

        return dp[word1.size()][word2.size()];
    }
};