企业官网建设流程全解析

LeetCode-Book 题解：判断子序列（Is Subsequence）双指针贪心匹配的 Python / Java / C++ 实现

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book

导读

本篇基于 LeetCode-Book 仓库中《Krahets 笔面试精选 88 题》题单的 392. 判断子序列 题解，深入讲解"双指针 + 贪心"这一经典匹配思路：如何仅用一次线性扫描判断字符串s是否为字符串t的子序列。读完本文，你将掌握双指针贪心匹配的完整推导过程、三种主流语言的等价实现、复杂度边界分析，以及"单 T 匹配多 S"场景下的预处理进阶方案，并能直接复现本仓库对应的可运行测试代码。

题目背景：什么是子序列

给定字符串s和t，判断s是否为t的子序列（Subsequence）。

子序列的定义是：通过删除t中的部分字符（也可以不删除），在不改变剩余字符相对顺序的前提下，恰好可以得到s。

例如：

• s = "abc"，t = "ahbgdc"：删除t中的'h'、'g'后得到"abc"，且顺序保持不变，因此返回true；
• 若s = "axc"，t = "ahbgdc"：无论删除哪些字符都无法在不改变顺序的情况下得到"axc"，因此返回false。

需要特别强调的是，子序列与子串（Substring）不同：子串要求字符在原串中连续出现，而子序列只要求相对顺序一致、允许中间跳过任意多个字符。这一区别正是本题"贪心匹配"可行性的根本来源。

核心思路：双指针贪心匹配

原文档给出的解题思路非常凝练：设置双指针i、j分别指向字符串s、t的首个字符，然后遍历字符串t，依据字符是否相等决定指针的移动方式：

• 当s[i] == t[j]时，代表匹配成功，此时同时执行i++、j++；
  • 进而，若i已走过s尾部，代表s是t的子序列，此时应提前返回true；
• 当s[i] != t[j]时，代表匹配失败，此时仅执行j++（继续向后寻找t中能与s[i]匹配的字符）；
• 若遍历完整个字符串t后，s仍未遍历完，说明t中剩余的字符不足以完成全部匹配，返回false。

为什么贪心是正确的

本题可以放心采用贪心策略，其正确性来源于一个关键事实：s中的每个字符越早在t中被匹配到，后续字符可选的匹配范围就越大，越不可能错过可行解。

换句话说，当指针i指向的字符在t的当前位置j处匹配成功时，我们立即消费这个匹配并推进i，而不是尝试让s[i]去匹配t中更靠后的同值字符。因为一旦当前位置就能匹配，把它让给后面相同字符并不会带来任何额外收益——两个相同字符在t中的相对位置中，靠前的位置只会给后续匹配留出更充裕的空间。这一性质保证了贪心选择的每一步都不会破坏最终解的存在性，从而在单次线性扫描内得到正确结论。

算法流程拆解

以s = "abc"、t = "ahbgdc"为例，逐步模拟指针移动过程：

可以看到，s的三个字符在t中被依次按顺序找到，且每次匹配成功后都立即推进i，这正是双指针贪心匹配的直观形态。

代码实现：三种语言等价写法

原文档给出了 Python、Java、C++ 三种语言的完整实现，下面逐一呈现并说明其细节。

Python 实现

class Solution: def isSubsequence(self, s: str, t: str) -> bool: if not s: return True i = 0 for c in t: if s[i] == c: i += 1 # 若已经遍历完 s ，则提前返回 true if i == len(s): return True return False

注意 Python 版本对空字符串s的提前处理：if not s: return True。因为空串是任意字符串的子序列，直接返回true既符合语义，也避免了空串时s[0]的索引越界问题。

Java 实现

class Solution { public boolean isSubsequence(String s, String t) { if (s.length() == 0) return true; for (int i = 0, j = 0; j < t.length(); j++) { if (s.charAt(i) == t.charAt(j)) { // 若已经遍历完 s ，则提前返回 true if (++i == s.length()) return true; } } return false; } }

Java 版将双指针i、j统一写在for循环中：i为s的下标（仅在匹配成功时通过前置自增++i推进），j为t的遍历下标（每轮循环自动推进）。++i == s.length()的写法在推进i的同时立即判断是否已遍历完s，代码更加紧凑。

C++ 实现

class Solution { public: bool isSubsequence(string s, string t) { if (s.size() == 0) return true; for (int i = 0, j = 0; j < t.size(); j++) { if (s[i] == t[j]) { // 若已经遍历完 s ，则提前返回 true if (++i == s.size()) return true; } } return false; } };

C++ 版本与 Java 版本结构完全一致，仅将length()换为size()。三种语言的循环逻辑、指针推进时机、提前返回条件一一对应，便于横向对比理解。

复杂度分析

• 时间复杂度 $O(N)$：其中 $N$ 为字符串t的长度。指针j随遍历推进，最差情况下需完整遍历t一次（如s的最后一个字符位于t的末尾），而指针i至多推进len(s)次。整体为线性扫描，时间复杂度 $O(N)$。
• 空间复杂度 $O(1)$：i、j两个指针变量只使用常数大小的额外空间，不随输入规模增长。

该复杂度分析意味着：即使t非常长，本解法也只需要一次完整遍历即可给出结论，这在字符串匹配类问题中是最优的量级。

边界情况与易错点

结合原文档与实现细节，有以下几个容易忽略的边界情况：

1. 空串s：必须直接返回true。若不加保护直接访问s[0]/s.charAt(0)/s[0]，在部分语言中会抛出越界异常。
2. s长度大于t：由于s的所有字符都需要在t中按序找到，当s比t还长时必然返回false。本算法无需显式判断该情况——循环结束后i一定未走完s，自然返回false。
3. 提前返回：当i已推进到len(s)（即s全部匹配完成）时立即返回true，避免对t剩余部分做无谓遍历。这是将最差复杂度从"必然扫完t"优化为"s匹配完成即终止"的关键。
4. s == t：两串完全相等时，每个字符依次匹配成功，最后一次匹配后i == len(s)提前返回true，符合"删除 0 个字符"即得到子序列的定义。

结合仓库源码：可运行测试验证

本仓库在 selected_coding_interview/codes 目录下为本题提供了完整的可运行代码与驱动测试：

• lc_392_is_subsequence.py：Python 实现附带了内置测试用例，取s = "abc"、t = "ahbgdc"，期望输出为True，通过Solution().isSubsequence(...)直接运行即可复现结果；
• lc_392_is_subsequence.java：Java 版在main方法中同样以"abc"、"ahbgdc"为输入，声明expected_output = true并通过Solution slt = new Solution()调用后打印结果，验证逻辑与 Python 版保持一致；
• lc_392_is_subsequence_s1.cpp：C++ 版以Solution类实现核心算法，驱动代码预留了测试用例与调用入口（// TODO: Add specific test case），可作为独立编译验证的起点。

仓库中三种语言的实现与本文讲解的算法完全对应，其中include头文件（如 Python 的 include 目录）为代码运行提供统一的辅助库，class Solution的题解代码与驱动测试代码分离的组织方式，也便于读者直接抽取isSubsequence方法用于 LeetCode 提交。

进阶延伸：大量 S 匹配同一个 T 的预处理方案

原文档聚焦于单次匹配，这里补充一个高频面试追问场景：若存在大量（例如 10⁴ 个）不同的s需要依次判断是否为同一个t的子序列，双指针贪心的 $O(|s| + |t|)$ 单次复杂度会退化为总复杂度 $O(\sum|s_i| + k \cdot |t|)$，t被反复完整扫描，代价过高。

此时可以对t做预处理，将每个字符在t中出现的位置按下标有序存储（如pos[26]数组，每个元素是一个递增的下标列表），然后对每个s贪心查找：

1. 维护一个游标idx，表示t中当前可用的最小匹配位置；
2. 遍历s的每个字符c，在pos[c]中二分查找第一个大于idx的下标p；
3. 若找不到则说明匹配失败，返回false；否则令idx = p，继续下一个字符。

预处理复杂度 $O(|t|)$，之后每个s的匹配复杂度为 $O(|s| \log |t|)$，整体远优于反复线性扫描。这一方案本质仍是贪心——每次取t中"最早可用的匹配位置"，与本题双指针思路一脉相承，可作为面试中展示思维深度的加分项。

小结

• 核心结论：判断子序列可借助双指针贪心在 $O(N)$ 时间、$O(1)$ 空间内完成，其中 $N$ 为t的长度；
• 贪心依据：s的每个字符在t中越早匹配，后续匹配空间越大，提前消费匹配不会破坏最优解；
• 实现要点：空串s提前返回true、匹配完成立即提前返回、遍历完t后s未走完则返回false；
• 实战价值：该模式可自然迁移到"字符串按序匹配""双指针扫描"一类问题，并可通过预处理 + 二分查找升级为多模式匹配方案。

如需查看本题完整题解与可运行代码，可直接访问仓库中的 392. 判断子序列 文档及 Python、Java、C++ 三份实现。

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book