1652408082(1).png

思路

常规双指针

常规的思路不要忘记，比如双指针法【不要被指针吓到啦，其实就是s[i] 和t[j]】

  1. var isSubsequence = function(s, t) {
  2. //    双指针法
  3. // 注意：题目已经约束，s是否为t的子序列
  4.     let m =s.length
  5.     let n =t.length
  6.     // 定义两个指针
  7.     let i =0,j=0
  8.     while(i<m&&j<n){
  9.         if(s[i]===t[j]){
  10.             i++
  11.         }
  12.         j++
  13.     }
  14.     // i等于s的长度，则代表s能在t中全匹配
  15.     return i===m
  17. };

时间复杂度O（n+m）
空间O（1）

通过求公共子序列长度进而判断的DP法

在确定递推公式的时候，首先要考虑如下两种操作，整理如下：

  • if (s[i - 1] == t[j - 1])
    • t中找到了一个字符在s中也出现了
  • if (s[i - 1] != t[j - 1])
    • 相当于t要删除元素，继续匹配

if (s[i - 1] == t[j - 1])，那么dp[i][j] = dp[i - 1][j - 1] + 1;，因为找到了一个相同的字符，相同子序列长度自然要在dp[i-1][j-1]的基础上加1
if (s[i - 1] != t[j - 1])，此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了，即：dp[i][j] = dp[i][j - 1];
这个递推公式唯一的疑问点在这里，就是为什么不像1143那样求公共子序列时，通过dp[i][j-1]和dp[i-1][j]二者判断得出结果？
这是因为！这里作为子序列的s我们要全部匹配上！所以删除匹配操作只能应用在t身上。所以当s[i-1] !== t[j-1]时，只能从dp[i][j-1]身上推出。
举例：s是ab，t是abc，此时b!== c，那么s这只能和t删除c的剩余部分，ab继续判断是否为子序列，而不是a和abc判断。

const isSubsequence = (s, t) => {
    // s、t的长度
    const [m, n] = [s.length, t.length];
    // dp全初始化为0
    const dp = new Array(m + 1).fill(0).map(x => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            // 更新dp[i][j]，两种情况
            if (s[i - 1] === t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = dp[i][j - 1];
            }
        }
    }
    // 遍历结束，判断dp右下角的数是否等于s的长度
    return dp[m][n] === m ? true : false;
};

官方DP法，可以解决如果有n个s子序列需要匹配的情况

//dp解法
    bool isSubsequence(string s, string t){
        int n = s.length(),m = t.length();
        //dp数组dp[i][j]表示字符串t以i位置开始第一次出现字符j的位置
        vector<vector<int>> dp(m + 1,vector<int> (26,0));

        //初始化边界条件，dp[i][j] = m表示t中不存在字符j
        for(int i=0;i<26;i++){
            dp[m][i] = m;
        }

        //从后往前递推初始化dp数组
        for(int i = m - 1;i>=0;i--) {
            for(int j=0;j<26;j++){
                if(t[i] == 'a' + j){
                    dp[i][j] = i;
                }else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }

        int add = 0;
        for(int i = 0;i<n;i++){
            //t中没有s[i] 返回false
            if(dp[add][s[i] - 'a'] == m){
                return false;
            }
            //否则直接跳到t中s[i]第一次出现的位置之后一位
            add = dp[add][s[i] - 'a'] + 1;
        }
        return true;
    }

哎哎哎我的JS写法就是不能A全部，明明逻辑是一样的啊啊啊啊啊啊

因为我这个傻子，创建二维的时候直接fill了啊啊啊

//   官方DP，为了进阶做法
    let m =s.length
    let n =t.length
    //dp的含义是：字符j（属于26个字符之一），从i位置开始第一次出现的位置
    ---大bug：let dp =new Array(n+1).fill(()=>new Array(26).fill(0))
    let dp =new Array(n+1).fill().map(()=>new Array(26).fill(0))
    for(let i=0;i<26;i++){
        dp[n][i] =n //初始化dp[n]为n,则代表在t中都不存在这些字符
    }

    // 从后往前遍历
    for(let i=n-1;i>=0;i--){
        for(let j=0;j<26;j++){
            if(t[i].charCodeAt()=='a'.charCodeAt()+j){            
                //注意JS的编码转换
                // 字符与数字之间差了‘a’，编码问题
                dp[i][j] =i
            }else{
                // 
                dp[i][j] =dp[i+1][j]
            }
        }
    }

// 如果有n个字符串s需要匹配，只要这里再套一个循环就可以了。时间复杂度是 xm+n*【字符长度】

    let add =0

    for(let i=0;i<m;i++){
        console.log(dp[add][s[i].charCodeAt()-'a'.charCodeAt()])
        // t中没有s[i]，只要有一个s字符不出现在t中，都不可能是子序列
        if(dp[add][s[i].charCodeAt()-'a'.charCodeAt()] ==n){
            return false
        }
        //否则直接跳到t中s[i]第一次出现的位置之后一位
        add =dp[add][s[i].charCodeAt()-'a'.charCodeAt()] +1

    }

    return true