目录

lc583.两个字符串的删除操作

Shen 收录于每日一题

2021-09-25 约 405 字预计阅读 1 分钟

目录

583.两个字符串的删除操作

最长公共子序列

给定两个字符串word1和word2，找出使两个字符串变为相同需要删除的字母的最少的个数
可以把这个问题转换为最长公共子序列问题，假设word1.size() = n,word2.size() = m，最长公共子序列的长度为k，那么两个字符串需要删除的最少的字母的个数就是等于n + m - 2k
最长公共子序列动态规划状态表示f[i][j]表示长度为i的word1与长度为j的word2的最长公共子序列的长度
对于长度分别为i,j，word1[i - 1]==word2[j - 1]时,f[i][j] = f[i - 1][j - 1] + 1，否则为max(f[i-1][j], f[i][j-1])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
public:
    int minDistance(string word1, string word2) {
        // 最长公共子序列
        // f[i][j]
        // word1长度为i，word2长度为j的最长公共子序列
        int n = word1.size(), m = word2.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));

        f[0][0] = 0;

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(word1[i - 1] == word2[j - 1]){
                    f[i][j] = f[i - 1][j - 1] + 1;
                }else{
                    f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }

        return n - f[n][m] + m - f[n][m];
    }
};