What is the easiest way to check if s is a subsequence of t?

Use a two pointers approach: iterate through t, moving the s pointer when characters match, returning true if s is fully traversed.

How does dynamic programming improve the Is Subsequence problem?

DP allows precomputing next character positions in t, reducing repeated scans and enabling fast queries when checking multiple s strings against the same t.

Can I use recursion for this problem?

Yes, but simple recursion without memoization may exceed time limits on longer t strings; iterative two pointers or DP is safer.

What should I watch out for with empty strings?

An empty s is always a subsequence of any t, but an empty t cannot contain any non-empty s; handle these as special cases.

Is this problem pattern always solved with two pointers?

Two pointers is the canonical approach for single queries, but DP or binary search optimizations are preferred when multiple queries target the same t.

#392

Easy

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如， "ace" 是 "abcde" 的一个子序列，而 "aec" 不是）。进阶：如果有大量输入的 S，称作 S1, S2, ... …

双指针字符串动态规划

题目描述

给定字符串 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 <= 100
0 <= t.length <= 10^4
两个字符串都只由小写字符组成。

lightbulb

解题思路

方法一：双指针

我们定义两个指针 $i$ 和 $j$ ，分别指向字符串 $s$ 和 $t$ 的初始位置。每次我们比较两个指针指向的字符，如果相同，则两个指针同时右移；如果不同，则只有 $j$ 右移。当指针 $i$ 移动到字符串 $s$ 的末尾时，说明 $s$ 是 $t$ 的子序列。

时间复杂度 $O(m + n)$ ，其中 $m$ 和 $n$ 分别是字符串 $s$ 和 $t$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i = j = 0
        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                i += 1
            j += 1
        return i == len(s)

speed

复杂度分析

指标	值
时间	complexity varies: simple two pointers is O(n) with n = t.length; DP preprocessing is O(n _26) and query per s is O(m) with m = s.length; binary search approach preprocesses t in O(n) and answers each s in O(m log k), where k is average occurrences per character. Space complexity ranges from O(1) for two pointers to O(n_ 26) for DP tables.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on maintaining character order while scanning t; interviewer may hint at pointer misalignment.
question_mark
Expect discussion of repeated queries, signaling a DP or preprocessed optimization.
question_mark
Be ready to explain why naive nested loops fail with longer t, showing awareness of time complexity.

warning

常见陷阱

外企场景

error
Incorrectly incrementing pointers can skip valid matches, producing false negatives.
error
Confusing contiguous substring with subsequence leads to wrong logic.
error
Not handling empty s or t properly may cause boundary errors or incorrect returns.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Check if s is a subsequence of multiple t strings efficiently using DP preprocessing.
arrow_right_alt
Return the length of the longest subsequence of s present in t.
arrow_right_alt
Allow wildcard characters in s that can match any single character in t.

help

常见问题

外企场景

继续练习

#647 回文子串 #5 最长回文子串 #838 推多米诺