判断子序列
难度:
标签:
题目描述
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
致谢：
特别感谢 @pbrother 添加此问题并且创建所有测试用例。
示例 1：
输入：s = "abc", t = "ahbgdc" 输出：true
示例 2：
输入：s = "axc", t = "ahbgdc" 输出：false
提示：
0 <= s.length <= 1000 <= t.length <= 10^4- 两个字符串都只由小写字符组成。
代码结果
运行时间: 15 ms, 内存: 16.0 MB
/*
* 思路：
* 使用 Java Stream API 简化实现。
* 通过对 t 进行过滤，保留那些与 s 中对应字符匹配的字符。
* 最终检查保留下来的字符是否能组成 s。
*/
import java.util.stream.IntStream;
public class Solution {
public boolean isSubsequence(String s, String t) {
int[] index = {0};
return t.chars().filter(c -> index[0] < s.length() && c == s.charAt(index[0])).count() == s.length();
}
}解释
方法:
该题解采用了双指针的思路。用两个指针i和j分别指向字符串s和t的开头。遍历字符串t，如果当前字符t[j]等于s[i]，则i向右移动。最后判断i是否等于s的长度，如果等于则说明s是t的子序列，否则不是。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在进阶问题中，当有大量的S输入时，需要考虑修改代码？当前的双指针逻辑是否适用于处理大量数据？
▷🦆
你能详细解释为什么在判断s是否为空字符串时，可以直接返回True吗？这里是否考虑了所有可能的场景？
▷🦆
在算法中，如果s的长度大于t的长度，是否有必要开始遍历t字符串？
▷🦆
如果t中的字符顺序与s中的字符顺序不一致，但所有字符都存在，此算法是否仍然返回false？
▷相关问题
匹配子序列的单词数
给定字符串 s 和字符串数组 words, 返回 words[i] 中是s的子序列的单词个数 。
字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。
- 例如，
“ace”是“abcde”的子序列。
示例 1:
输入: s = "abcde", words = ["a","bb","acd","ace"] 输出: 3 解释: 有三个是 s 的子序列的单词: "a", "acd", "ace"。
Example 2:
输入: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"] 输出: 2
提示:
1 <= s.length <= 5 * 1041 <= words.length <= 50001 <= words[i].length <= 50words[i]和 s 都只由小写字母组成。