leetcode 字符串

1143. 最长公共子序列 

. - 力扣（LeetCode）

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m=text1.length();
        int n=text2.length();
        vector<vector<int>>f(m+1,vector<int>(n+1,0));
        
        
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(text1[i-1]==text2[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 f[m][n];

    }
};

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

. - 力扣（LeetCode）

方法一：先算出最长公共子序列，在分别（word1.length - f[m][n]）+ (word2.length-f[m][n]);

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m=word1.length();
        int n=word2.length();
        vector<vector<int>> f(m+1,vector<int>(n+1, 0));
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;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 m+n-2*f[m][n];
    }
};

方法二：直接定义f[i][j]：word1[0;i]和word2[0:j]变成一样的最小删除次数。

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m=word1.length();
        int n=word2.length();
        vector<vector<int>> f(m+1,vector<int>(n+1,0));
        for(int i=0;i<=m;i++)
            f[i][0] = i;
        for(int j=0;j<=n;j++)
            f[0][j] = j;

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