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
:- 指针
i
用于指向s
中的当前字符; - 指针
j
用于指向t
中的当前字符。
- 指针
- 遍历
t
:- 如果
s[i] == t[j]
,说明匹配上了,i++
。 - 始终移动
j
,以确保字符的顺序性。
- 如果
- 如果
i == s.length
,说明s
的所有字符都能按顺序匹配上,返回true
;否则返回false
。
复杂度分析
- 时间复杂度:
O(n)
,其中n
是字符串t
的长度。 - 空间复杂度:
O(1)
。
进阶:二分法(进阶版)
预处理
t
的索引位置:- 先用一个哈希表
indexMap
存储t
中每个字符的所有出现位置(按照索引升序)。
- 先用一个哈希表
二分查找加速匹配:
- 遍历
s
中的每个字符,使用二分查找定位该字符在t
中的下一个匹配位置。 - 在哈希表中,快速找到
t
中大于当前指针j
的最小索引。 - 如果找不到,说明无法匹配当前字符,返回
false
。
- 遍历
二分查找函数
left_bound
:在升序数组中找到第一个大于等于target
的位置,若不存在返回-1
。
复杂度分析
时间复杂度:
O(n + m log n)
,其中n
是字符串t
的长度,m
是s
的长度。- 预处理:遍历
t
构建哈希表,时间复杂度为O(n)
。 - 匹配:对于每个字符,在哈希表中查找位置,时间复杂度为
O(m log n)
。 - 总复杂度:
O(n + m log n)
。
- 预处理:遍历
空间复杂度:
O(n)
,使用一个哈希表存储索引位置。
代码
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isSubsequence = function (s, t) {
let i = 0; // 指向 s 的指针
let j = 0; // 指向 t 的指针
while (i < s.length && j < t.length) {
if (s[i] == t[j]) {
i++; // 匹配上时移动 s 的指针
}
j++; // 始终移动 t 的指针
}
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]] = [];
}
indexMap[t[i]].push(i);
}
// 在 t 上的指针
let j = 0;
for (let i = 0; i < s.length; i++) {
// 如果 s[i] 不在 t 中,直接返回 false
if (!indexMap[s[i]]) return false;
// 找到大于等于 j 的下一个位置
let pos = left_bound(indexMap[s[i]], j);
if (pos == -1) return false;
// 更新指针位置
j = indexMap[s[i]][pos] + 1;
}
return true;
};
// 二分查找:找到大于等于 target 的最小位置
var left_bound = function (arr, target) {
let left = 0,
right = arr.length;
while (left < right) {
let mid = left + Math.floor((right - left) / 2);
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left == arr.length ? -1 : left;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
792 | 匹配子序列的单词数 | 字典树 数组 哈希表 4+ | 🟠 | 🀄️ 🔗 | |
1055 | 形成字符串的最短路径 🔒 | 贪心 双指针 字符串 1+ | 🟠 | 🀄️ 🔗 | |
2486 | 追加字符以获得子序列 | 贪心 双指针 字符串 | 🟠 | 🀄️ 🔗 | |
2825 | 循环增长使字符串子序列等于另一个字符串 | [✓] | 双指针 字符串 | 🟠 | 🀄️ 🔗 |