LeetCode 392. 判断子序列

题目描述

392. 判断子序列

思路分析

✅ 解法一:双指针

核心思想:

  • 用两个指针 ij 遍历字符串 st
  • 每当 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),只用常数变量做指针控制

➡️ 点击查看 Java 题解

1
write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2025/70984513
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处!