✅392. 判断子序列

[Ray-56]

392. 判断子序列

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

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。

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

示例1：

s = "abc", t = "ahbgdc"

返回 true

示例2：

s = "axc", t = "ahbgdc"

返回 false.

后续挑战:

如果有大量输入的 S，称作S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

[Ray-56]

dp解

dp[i][j] = boolean，i表示字符串s的下标，j表示字符串t的下标，值为在这两个下标是否为子序列

创建dp[s.length+1][t.length+1]的数组

方便使用，我们将dp[i] = [true, ..., true]

s[i - 1] === t[j - 1] 时，当前就为dp中的这两个下标的值

不等时，赋值为上一个 dp[i][j] = dp[i][j - 1]

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function(s, t) {
    // 动态规划
    // dp[i][j] = boolean
    const sLen = s.length;
    const tLen = t.length;
    if (!sLen) return true;
    if (!tLen) return false;
    const dp = new Array(sLen + 1).fill(0).map(() => new Array(tLen + 1).fill(false));
    dp[0] = new Array(tLen).fill(true);
    for (let i = 1; i <= sLen; i++) {
        for (let j = 1; j <= tLen; j++) {
            if (s[i - 1] === t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = dp[i][j - 1];
            }
        }
    }
    return dp[sLen][tLen];
};

双指针解

i 表示 s 的位置，j 表示 t 的位置，

j 每次都需要移动，相等时将 i 向后移动

判断 i 是否为 s 的长度

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function(s, t) {
    // 双指针
    const sLen = s.length;
    const tLen = t.length;
    let i = 0;
    let j = 0;
    while (i < sLen && j < tLen) {
        if (s[i] === t[j]) {
            i++;
        }
        j++;
    }
    return i === sLen;
};