392. 判断子序列
392. 判断子序列
🟢 🔖 双指针
字符串
动态规划
🔗 力扣
LeetCode
题目
Given two strings s
and t
, return true
ifs
_is a subsequence of _t
, orfalse
otherwise.
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace"
is a subsequence of " _a_ b _c_ d _e_ "
while "aec"
is not).
Example 1:
Input: s = "abc", t = "ahbgdc"
Output: true
Example 2:
Input: s = "axc", t = "ahbgdc"
Output: false
Constraints:
0 <= s.length <= 100
0 <= t.length <= 10^4
s
andt
consist only of lowercase English letters.
Follow up: Suppose there are lots of incoming s
, say s1, s2, ..., sk
where k >= 109
, and you want to check one by one to see if t
has its subsequence. In this scenario, how would you change your code?
题目大意
给定字符串 s
和 t
,判断 s
是否为 t
的子序列。字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"
是"abcde"
的一个子序列,而"aec"
不是)。
进阶 :如果有大量输入的 S
,称作 S1, S2, ... , Sk
其中 k >= 10亿
,你需要依次检查它们是否为 T
的子序列。在这种情况下,你会怎样改变代码?
解题思路
思路一:双指针
使用两个指针 i
、j
分别指向字符串 s
和 t
,然后对两个字符串进行遍历,时间复杂度 O(n)
。
- 遇到
s[i] == t[j]
的情况,则i
向右移。 - 不断右移
j
。 - 如果超过
s
或t
的长度则跳出。 - 最后判断指针
i
是否指向了s
的末尾,即:判断i
是否等于s
的长度。如果等于,则说明s
是t
的子序列,如果不等于,则不是。
进阶:二分思路
二分思路主要是对 t
进行预处理,用一个字典将每个字符出现的索引位置按顺序存储下来,比如 "abacb"
的字典为:{a: [0, 1], b: [1, 4], c: [3]}
,这样我们不需要每次都遍历 t
,只需查看字典中,是否有满足要求的索引即可。
代码
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isSubsequence = function (s, t) {
let i = 0;
let j = 0;
while (i < s.length && j < t.length) {
if (s[i] == t[j]) {
i++;
}
j++;
}
return i == s.length;
};
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isSubsequence = function (s, t) {
let indexMap = {};
for (let i = 0; i < t.length; i++) {
if (!indexMap[t[i]]) {
indexMap[t[i]] = new Array();
}
indexMap[t[i]].push(i);
}
// 串 t 上的指针
let j = 0;
for (let i = 0; i < s.length; i++) {
// 整个 t 压根儿没有这个字符
if (!indexMap[s[i]]) return false;
let pos = left_bound(indexMap[s[i]], j);
console.log(s[i], pos, j);
// 二分搜索区间中没有找到字符 c
if (pos == -1) return false;
// 向前移动指针 j
j = indexMap[s[i]][pos] + 1;
}
return true;
};
// 查找左侧边界的二分查找
var left_bound = function (arr, target) {
let left = 0,
right = arr.length;
while (left < right) {
let mid = left + Math.floor((right - left) / 2);
if (target > arr[mid]) {
left = mid + 1;
} else {
right = mid;
}
}
// 如果 left 越界 说明数组中不存在 target
if (left == arr.length) {
return -1;
}
return left;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
792 | 匹配子序列的单词数 | 字典树 数组 哈希表 4+ | ||
1055 | 形成字符串的最短路径 🔒 | 贪心 双指针 字符串 1+ | ||
2486 | 追加字符以获得子序列 | 贪心 双指针 字符串 | ||
2825 | 循环增长使字符串子序列等于另一个字符串 | 双指针 字符串 |