附JSPythonC题解-Leetcode-面试150题6

JAY.LIN 收录于 Leetcode

2025-03-07 约 509 字预计阅读 2 分钟

https://bing.ee123.net/img/rand?artid=146095627

[附JS、Python、C++题解] Leetcode 面试150题（6）

一、题目

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

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

进阶：

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

二、思路

双指针，一个遍历s，一个遍历t，不匹配就移动指针；
要关注出现顺序是否一致【相对位置】；
大量输入的情况要求时间复杂度和空间复杂度最优；
注意边界条件！

如果 s 是空字符串，直接返回 true ，因为空字符串是任何字符串的子序列。
如果 t 是空字符串，但 s 不是空字符串，直接返回 false ，因为非空字符串不可能是空字符串的子序列。

三、代码

① JavaScript：

function isSubSeq (s,t){
    let i =0;
    if(s.length > t.length ){
        return false;
    }
    for(let j = 0; j<s.length; j++){
        while (i < t.length && s[j] !== t[i]) {
            i++;
        }
        if (i === t.length) {
            return false;
        }
        i++;
    }
    return true;
}

更高效的一种解法：

function isSubSq(s, t) {
    let j = 0;
    for(let i = 0; i < t.length; i++) {
        if(s[j] === t[i]) {
            ++j;
        }
    }
    return j === s.length;
}

② Python：

def isSubSq (s,t):
    j = 0
    for i in range(0,len(t)):
        if s[j] == t[i]:
            j += 1
    return j==len(s)

③ C++：

bool isSubSq(const std::string& s, const std::string& t) {
    int j = 0; 
    for (int i = 0; i < t.length(); i++) { 
        if (s[j] == t[i]) { 
            j++; 
        }
    }
    return j == s.length(); 
}