代码随想录Day57、58|392.判断子序列|115.不同的子序列|583.两个字符串的删除操作|72.编辑距

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; //匹配，则长度加1 else 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]; } };