LeetCode 392. 判断子序列
题目描述
思路分析
✅ 解法一:双指针
核心思想:
- 用两个指针
i
和j
遍历字符串s
和t
- 每当
s[i] == t[j]
,说明匹配成功,i++
- 始终
j++
,尝试在t
中找到下一个匹配字符终止条件:
- 如果
i == len(s)
,说明s
全部字符都能在t
中按顺序找到,返回true
- 否则返回
false
参考代码
1
2
3
4
5
6
7
8
9
10
func isSubsequence(s string, t string) bool {
i, j := 0, 0
for j < len(t) {
if i < len(s) && s[i] == t[j] {
i++
}
j++
}
return i == len(s)
}
1
2
3
4
5
6
7
8
9
10
func isSubsequence(s string, t string) bool {
i, j := 0, 0
for i < len(s) && j < len(t) {
if s[i] == t[j] {
i++ // 匹配到了,移动 s 的指针
}
j++ // 无论是否匹配都要移动 t 的指针
}
return i == len(s)
}
时间复杂度:O(n),其中 n 为
t
的长度(最坏要遍历完整个 t)空间复杂度:O(1),只用常数变量做指针控制
1
write your code here
CC BY-NC-SA 4.0
许可协议,转载请注明出处!
本博客所有文章除特别声明外,均采用