392. 判断子序列

        

class Solution {
public:bool isSubsequence(string s, string t) {int m = s.size();int n = t.size();vector<vector<int>> f(m+1,vector<int>(n+1,0)); //f[i][j]:s前i-1个字符，t前j-1个字符中字符数相等的个数。for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(s[i-1]==t[j-1])f[i][j]=f[i-1][j-1]+1; //匹配，则长度加1else f[i][j] = f[i][j-1];  //若不匹配，则删除最后一个字符}}return f[m][n]==m;}
};

115. 不同的子序列

class Solution {
public:int numDistinct(string s, string t) {int mod = 1e9 + 7;int m = s.size();int n = t.size();vector<vector<int>> f(m+1,vector<int>(n+1,0));for (int i = 0; i < m; i++) f[i][0] = 1;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(s[i-1]==t[j-1]){f[i][j]=(f[i-1][j-1]+f[i-1][j])%mod; }else{f[i][j]=f[i-1][j]%mod;//两个字符串最后一个字符不相等，故删去最后一个字符重新匹配}}}return f[m][n];}
};

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

class Solution {
public:int minDistance(string word1, string word2) {int m = word1.size();int n = word2.size();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];  //两个字符串各减去公共字符串的长度即为需要删除的步数}
};

72. 编辑距离

        

class Solution {
public:int minDistance(string word1, string word2) {int n=word1.size();int m=word2.size();vector<vector<int>>f(n+1,vector<int>(m+1,0)); //f[i][j]:word1前i个字符转换为word2前j个字符需要的步数for(int i=0;i<=n;i++){  //赋初值f[i][0]=i;  }for(int j=0;j<=m;j++){f[0][j]=j;}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];}else {f[i][j]=min(f[i-1][j]+1,min(f[i][j-1]+1,f[i-1][j-1]+1));//最后一位不相等，方法一：删除word1最后一个字符//方法二：删除word2最后一个字符，等价于word1增加一个字符//方法三：替换最后一个字符，即f[i-1][j-1]+1。}}}return f[n][m];}
};