代码随想录算法训练营第36期DAY58

DAY58

今天的主题是：编辑距离。在字符串进行增删字符的操作。

392判断子序列，简单

首先想到快慢双指针：

通过了，很好：

1. class Solution {
2. public:
3.     bool isSubsequence(string s, string t) {
4.         int slow=0;
5.         for(int fast=0;fast<t.size();fast++){
6.             if(t[fast]==s[slow]) slow++;
7.         }
8.         if(slow==s.size()) return true;
9.         return false;
10.     }
11. };

动态规划：没有想法尤其是遍历顺序及递推公式（不要用bool 就好想了 ），积累经验吧：

要看出来，这题和求最长公共子序列是一样的，递推公式有点区别，但也是继承。

使用二维数组来记录字符比较结果。

Dp[i][j] 相同长度。

Code:

写了两个for循环，运行时间竟然是最优的，击败100%，奇怪了

1. class Solution {
2. public:
3.     bool isSubsequence(string s, string t) {
4.         vector<vector<int>> dp(s.size()+1,vector<int>(t.size()+1,0));
5.         for(int i=1;i<=s.size();i++){
6.             for(int j=1;j<=t.size();j++){
7.                 if(s[i-1]==t[j-1]) dp[i][j]=dp[i-1][j-1]+1;
8.                 else dp[i][j]=dp[i][j-1];
9.             }
10.         }
11.         return dp[s.size()][t.size()]==s.size();
12.     }
13. };

115不同的子序列，困难

这题要做的要是编辑距离（仅删除似乎不够，还需要把删除的添加回来，但是这些操作都只在一个字符串上进行），积累经验：

显然如果是求连续子序列，就可以用KMP（记得复习KMP模板）；

尝试着写递推公式，纸质笔记：

Code:

注意取模操作。

1. class Solution {
2. public:
3.     long long pow(int n){
4.         return 1e9;
5.     }
6.     int numDistinct(string s, string t) {
7.         vector<vector<long long>> dp(s.size()+1,vector<long long>(t.size()+1));
8.         for(int i=1;i<s.size()+1;i++) dp[i][0]=1;
9.         for(int i=1;i<t.size()+1;i++) dp[0][i]=0;
10.         dp[0][0]=1;
11.         for(int i=1;i<=s.size();i++){
12.             for(int j=1;j<=t.size();j++){
13.                 if(s[i-1]==t[j-1]) dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%(int)(pow(9)+7);
14.                 else dp[i][j]=(dp[i-1][j])%(int)(pow(9)+7);
15.             }
16.         }
17.         return dp[s.size()][t.size()];
18.     }
19. };