【算法挨揍日记】day38——115. 不同的子序列、44. 通配符匹配

朴灿烈づ我的快乐病毒、 2024-02-05 12:56 61阅读 0赞

## 115. 不同的子序列 ##

[115. 不同的子序列][115.]

### 题目描述： ###

给你两个字符串 `s`和 `t` ，统计并返回在 `s` 的 **子序列** 中 `t` 出现的个数，结果需要对 109 + 7 取模。

### ![d63cbab95f9b43b6b69736a81db061ea.png][] 解题思路： ###

算法思路：

1.  状态表⽰：

对于两个字符串之间的  dp  问题，我们⼀般的思考⽅式如下：

i.  选取第⼀个字符串的  \[0, i\]  区间以及第⼆个字符串的  \[0, j\]  区间当成研究对象，结

合题⽬的要求来定义「状态表⽰」；

ii.  然后根据两个区间上「最后⼀个位置的字符」，来进⾏「分类讨论」，从⽽确定「状态转移

⽅程」。

我们可以根据上⾯的策略，解决⼤部分关于两个字符串之间的  dp  问题。

dp\[i\]\[j\]  表⽰：在字符串  s  的  \[0, j\]  区间内的所有⼦序列中，有多少个  t  字符串  \[0,

i\]  区间内的⼦串。

2.  状态转移⽅程：

⽼规矩，根据「最后⼀个位置」的元素，结合题⽬要求，分情况讨论：

i.  当  t\[i\] == s\[j\]  的时候，此时的⼦序列有两种选择：

•  ⼀种选择是：⼦序列选择  s\[j\]  作为结尾，此时相当于在状态  dp\[i - 1\]\[j - 1\]

中的所有符合要求的⼦序列的后⾯，再加上⼀个字符  s\[j\]  （请⼤家结合状态表⽰，

好好理解这句话），此时  dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\]  ；

•  另⼀种选择是：我就是任性，我就不选择  s\[j\]  作为结尾。此时相当于选择了状态

dp\[i\]\[j - 1\]  中所有符合要求的⼦序列。我们也可以理解为继承了上个状态⾥⾯的

求得的⼦序列。此时  dp\[i\]\[j\] = dp\[i\]\[j - 1\]  ；

两种情况加起来，就是  t\[i\] == s\[j\]  时的结果。

ii.  当  t\[i\] != s\[j\]  的时候，此时的⼦序列只能从  dp\[i\]\[j - 1\]  中选择所有符合要

求的⼦序列。只能继承上个状态⾥⾯求得的⼦序列，  dp\[i\]\[j\] = dp\[i\]\[j - 1\]  ；

综上所述，状态转移⽅程为：

▪  所有情况下都可以继承上⼀次的结果：  dp\[i\]\[j\] = dp\[i\]\[j - 1\]  ；

▪  当  t\[i\] == s\[j\]  时，可以多选择⼀种情况：  dp\[i\]\[j\] += dp\[i - 1\]\[j - 1\]

3.  初始化：

a.  「空串」是有研究意义的，因此我们将原始  dp  表的规模多加上⼀⾏和⼀列，表⽰空串。

b.  引⼊空串后，⼤⼤的⽅便我们的初始化。

c.  但也要注意「下标的映射关系」，以及⾥⾯的值要「保证后续填表是正确的」。

当  s  为空时，  t  的⼦串中有⼀个空串和它⼀样，因此初始化第⼀⾏全部为  1  。

4.  填表顺序：

「从上往下」填每⼀⾏，每⼀⾏「从左往右」。

5.  返回值：

根据「状态表⽰」，返回  dp\[m\]\[n\]  的值。

本题有⼀个巨恶⼼的地⽅，题⽬上说结果不会超过  int  的最⼤值，但是实际在计算过程会会超。为

了避免报错，我们选择  double  存储结果。

### 解题代码： ###

class Solution {
    public:
        int numDistinct(string s, string t) {
            int n=s.size();
            int m=t.size();
            vector<vector<double>>dp(m+1,vector<double>(n+1,0));
            s=" "+s;
            t=" "+t;
            for(int i=0;i<=n;i++)   dp[0][i]=1;
            for(int i=1;i<=m;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    if(t[i]==s[j])  dp[i][j]+=dp[i-1][j-1];
                    dp[i][j]+=dp[i][j-1];
                }
            }
            return dp[m][n];
        }
    };

## 44. 通配符匹配 ##

[44. 通配符匹配][44.]

### 题目描述： ###

给你一个输入字符串 (`s`) 和一个字符模式 (`p`) ，请你实现一个支持 `'?'` 和 `'*'` 匹配规则的通配符匹配：

*  `'?'` 可以匹配任何单个字符。
 *  `'*'` 可以匹配任意字符序列（包括空字符序列）。

判定匹配成功的充要条件是：字符模式必须能够 **完全匹配** 输入字符串（而不是部分匹配）。

![14e8c3d07e91428f9727e5c1d81da18a.png][]

### 解题思路： ###

算法思路：

1.  状态表⽰：

对于两个字符串之间的 dp 问题，我们⼀般的思考⽅式如下：

i.  选取第⼀个字符串的  \[0, i\]  区间以及第⼆个字符串的  \[0, j\]  区间当成研究对象，结

合题⽬的要求来定义「状态表⽰」；

ii.  然后根据两个区间上「最后⼀个位置的字符」，来进⾏「分类讨论」，从⽽确定「状态转移

⽅程」。

我们可以根据上⾯的策略，解决⼤部分关于两个字符串之间的  dp  问题。

因此，我们定义状态表⽰为：

dp\[i\]\[j\]  表⽰：  p  字符串  \[0, j\]  区间内的⼦串能否匹配字符串  s  的  \[0, i\]  区间内的

⼦串。

2.  状态转移⽅程：

⽼规矩，根据最后⼀个位置的元素，结合题⽬要求，分情况讨论：

i.  当  s\[i\] == p\[j\]  或  p\[j\] == '?'  的时候，此时两个字符串匹配上了当前的⼀个字

符，只能从  dp\[i - 1\]\[j - 1\]  中看当前字符前⾯的两个⼦串是否匹配。只能继承上个

状态中的匹配结果，  dp\[i\]\[j\] = dp\[i\]\[j - 1\]  ；

ii.  当  p\[j\] == '\*'  的时候，此时匹配策略有两种选择：

•  ⼀种选择是：  \*  匹配空字符串，此时相当于它匹配了⼀个寂寞，直接继承状态  dp\[i\]

\[j - 1\]  ，此时  dp\[i\]\[j\] = dp\[i\]\[j - 1\]  ；

•  另⼀种选择是：  \*  向前匹配  1 ~ n  个字符，直⾄匹配上整个  s1  串。此时相当于

从  dp\[k\]\[j - 1\] (0 <= k <= i)  中所有匹配情况中，选择性继承可以成功的

情况。此时  dp\[i\]\[j\] = dp\[k\]\[j - 1\] (0 <= k <= i)  ；

iii.  当  p\[j\]  不是特殊字符，且不与  s\[i\]  相等时，⽆法匹配。

三种情况加起来，就是所有可能的匹配结果。

综上所述，状态转移⽅程为：

▪  当  s\[i\] == p\[j\]  或  p\[j\] == '?'  时：  dp\[i\]\[j\] = dp\[i\]\[j - 1\]  ；

▪  当  p\[j\] == '\*'  时，有多种情况需要讨论：  dp\[i\]\[j\] = dp\[k\]\[j - 1\] (0 <=

k <= i)  ；

优化：当我们发现，计算⼀个状态的时候，需要⼀个循环才能搞定的时候，我们要想到去优化。优

化的⽅向就是⽤⼀个或者两个状态来表⽰这⼀堆的状态。通常就是把它写下来，然后⽤数学的⽅式

做⼀下等价替换：

当  p\[j\] == '\*'  时，状态转移⽅程为：

dp\[i\]\[j\] = dp\[i\]\[j - 1\] || dp\[i - 1\]\[j - 1\] || dp\[i - 2\]\[j - 1\]

......

我们发现  i  是有规律的减⼩的，因此我们去看看  dp\[i - 1\]\[j\]  ：

dp\[i - 1\]\[j\] = dp\[i - 1\]\[j - 1\] || dp\[i - 2\]\[j - 1\] || dp\[i - 3\]

\[j - 1\] ......

我们惊奇的发现，  dp\[i\]\[j\]  的状态转移⽅程⾥⾯除了第⼀项以外，其余的都可以⽤  dp\[i -

1\]\[j\]  替代。因此，我们优化我们的状态转移⽅程为：  dp\[i\]\[j\] = dp\[i - 1\]\[j\] ||

dp\[i\]\[j - 1\]  。

3.  初始化：

由于  dp  数组的值设置为是否匹配，为了不与答案值混淆，我们需要将整个数组初始化为

false  。

由于需要⽤到前⼀⾏和前⼀列的状态，我们初始化第⼀⾏、第⼀列即可。

◦  dp\[0\]\[0\]  表⽰两个空串能否匹配，答案是显然的， 初始化为  true  。

◦  第⼀⾏表⽰  s  是⼀个空串，  p  串和空串只有⼀种匹配可能，即  p  串表⽰为  "\*\*\*"  ，此时

也相当于空串匹配上空串。所以，我们可以遍历  p  串，把所有前导为  "\*"  的  p  ⼦串和空串

的  dp  值设为  true  。

◦  第⼀列表⽰  p  是⼀个空串，不可能匹配上  s  串，跟随数组初始化即可。

4.  填表顺序：

从上往下填每⼀⾏，每⼀⾏从左往右。

5.  返回值：

根据状态表⽰，返回  dp\[m\]\[n\]  的值。

### 解题代码： ###

class Solution
    {
    public:
     bool isMatch(string s, string p) 
     {
     int m = s.size(), n = p.size();
     s = " " + s, p = " " + p;
     vector<vector<bool>> dp(m + 1, vector<bool>(n + 1)); // 1. 创建 dp 表
     dp[0][0] = true; // 2. 初始化
     for(int j = 1; j <= n; j++)
     if(p[j] == '*') dp[0][j] = true;
     else break;
     // 3. 填表
     for(int i = 1; i <= m; i++)
     {
     for(int j = 1; j <= n; j++)
     {
     if(p[j] == '*')
     dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
     else
     dp[i][j] = (p[j] == '?' || s[i] == p[j]) && dp[i - 1][j - 
    1];
     }
     }
     // 4. 返回值
     return dp[m][n];
     }
    };

[115.]: https://leetcode.cn/problems/distinct-subsequences/
[d63cbab95f9b43b6b69736a81db061ea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/b951fc8e76e04f2a97176a6d23707fb5.png
[44.]: https://leetcode.cn/problems/wildcard-matching/
[14e8c3d07e91428f9727e5c1d81da18a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/1bcc6c8472384b68859eefd94b182db8.png