392.判断子序列

发表于： 分类于：
字数： 684 阅读：≈ 2分钟

😄392.判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，“ace"是"abcde"的一个子序列，而"aec"不是）。

思路

基本思想

判断一个字符串是不是另外一个字符串的子序列，可以转换一种思路，判断一个两个字符串的最长公共子序列的长度是多少，如果最长公共子序列的长度是s的长度，那么就可以说s是t的子序列

只要将问题转换成这个，就只需要在 1143题 的基础上增加一步判断，判断其最长公共子序列的长度是不是等于s的长度即可

而判断两个字符串的最长公共子序列的方法就是拿一个字符串的一个元素去与另外一个字符串的每个元素做对比，一旦出现匹配的元素，最长公共子序列的长度就递增，否则就说明有一个元素多余，此时换一种判断标准去更新dp数组

其中dp[i][j]表示以第i个元素和第j个元素结尾的两个字符串的最长公共子序列的长度

形成的判断逻辑为：

1
2
3
4
5
6

if(s[i]==t[j]){
    dp[i+1][j+1]=dp[i][j]+1;
}
else{
    dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
}

执行流程

  1. 初始化dp数组，使其元素全为零
  2. 遍历两个字符串，遍历的过程中更新dp数组
  3. 为了求最长公共子序列的长度，需要在更新的过程中记录出现的最大值
  4. 看最大值是不是s的长度，从而判断是不是t的子序列

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>>dp(s.size()+1,
                            vector<int>(t.size()+1,0));
        int res=0;
        for(int i=0;i<s.size();++i){
            for(int j=0;j<t.size();++j){
                if(s[i]==t[j]){
                    dp[i+1][j+1]=dp[i][j]+1;
                }else{
                    dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
                }
                res=max(res,dp[i+1][j+1]);
            }
        }
        return res==s.size();
    }
};

总结

主要是转换思想，先求两个字符串的最长公共子序列长度，最后在判断最长公共子序列的长度与s的长度是否相等，相等的话s就是t的子序列