583两个字符串的删除操作

关键词

字符串 动态规划

思路

要删除次数最少，那么应该尽可能找到两个字符串的公共部分
对于字符串A和字符串B的前i个字符和前j个字符，记录删除次数为dp[i][j]
他们是由前面的部分增长过来的，不难看出 dp 随 i, j 的增长而增长
如果两个末尾的字符相同，dp[i][j] = dp[i-1][j-1]
否则，删除某个末尾字符， dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1])

注意点

1. 任何字符串与空字符串匹配，需要全部删除
2. 注意是前i个字符（因为要考虑空串）

代码

class Solution {
public:
    int minDistance(string word1, string word2) {
        // base ops
        int m = word1.size(), n = word2.size();
        if (m == 0)
            return n;
        if (n == 0)
            return m;
        int dp[m+1][n+1];
        for (int j = 0; j <= n; ++j) {
            dp[0][j] = j;
        }
        for (int i=0; i <= m; ++i) {
            dp[i][0] = i;
        }
        //
        for (int i=1; i<=m; ++i) {
            for (int j=1; j<=n; ++j) {
                if (word1[i-1] == word2[j-1]) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        //
        return dp[m][n];

    }
};