力扣115. 不同的子序列 记忆化搜索法

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。

题目数据保证答案符合 32 位带符号整数范围。

示例 1：

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit
1
2
3
4
5
6
7

示例 2：

输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag
1
2
3
4
5
6
7
8
9

提示：

1 <= s.length, t.length <= 1000
s 和 t 由英文字母组成

错误解法，超时:

//回溯法 若s[0]==t[0] 则要么两个字符串都删去第一个进入下一轮回溯 要么只消去s[0] 
//若s[0]!=t[0] 则只能消去s[0]
int numDistinct(string s, string t) {
    if(t=="") return 1;//t已经被配对完毕 数量加1
    else{
        if(s.size()<t.size()) return 0;//已经无法完成配对 剪枝
        if(s[0]==t[0]) return numDistinct(s.substr(1),t)+numDistinct(s.substr(1),t.substr(1));
        else{
            int i=0;
            while(i<s.size()&&s[i]!=t[0]) ++i;
            if(i==s.size()) return 0;
            else return numDistinct(s.substr(i+1),t)+numDistinct(s.substr(i+1),t.substr(1));
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

正确解法，记忆化搜索：
执行用时：28 ms, 在所有 C++ 提交中击败了84.84%的用户
内存消耗：18.6 MB, 在所有 C++ 提交中击败了73.83%的用户

//常规dfs不行的原因是每层递归会去匹配s和t的每个下标是否相等 比如s[i]与t[j]
//若s[i]==t[j] 有配对或者不配对两个递归分支 每个递归分支又有更多的递归分支
//那么不可避免的 会有很多的重复计算
//为了避免重复计算 可以使用记忆化搜索 把已经搜索过的下标[i,j]的结果保存起来
//这样就节省了很多不必要的开销 使用unordered_map<pair<int>,int>来保存记忆数组最合适
//但是C++中没有给pair做Hash的函数，所以不能用pair作为unordered_map的key。
//但是,map里面是通过操作符<来比较大小，而pair是可以比较大小的。所以可以用map
map<pair<int,int>,int> my_map;
int dfs_memory(string &s, string &t,int i, int j){
    if( my_map.count({i,j})!=0)  return my_map[{i,j}];
    if(s.size()-i<t.size()-j) return 0;//已无法配对 剪枝
    if(j==t.size()) return 1;//配对完成 数量+1
    int cnt=0;
    cnt+=dfs_memory(s,t,i+1,j);//不匹配的情况
    if(s[i]==t[j])  cnt+=dfs_memory(s,t,i+1,j+1);
    my_map[{i,j}]=cnt;
    return cnt;
}

int numDistinct(string s, string t) {
    return dfs_memory(s,t,0,0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22