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 abct ahbgdc删除t中的h、g后得到abc且顺序保持不变因此返回true若s axct 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为例逐步模拟指针移动过程步骤指针i指向s指针j指向t字符比较动作1i0→aj0→a相等匹配成功i1、j12i1→bj1→h不等匹配失败仅j23i1→bj2→b相等匹配成功i2、j34i2→cj3→g不等匹配失败仅j45i2→cj4→d不等匹配失败仅j56i2→cj5→c相等匹配成功i3i len(s)提前返回true可以看到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非常长本解法也只需要一次完整遍历即可给出结论这在字符串匹配类问题中是最优的量级。边界情况与易错点结合原文档与实现细节有以下几个容易忽略的边界情况空串s必须直接返回true。若不加保护直接访问s[0]/s.charAt(0)/s[0]在部分语言中会抛出越界异常。s长度大于t由于s的所有字符都需要在t中按序找到当s比t还长时必然返回false。本算法无需显式判断该情况——循环结束后i一定未走完s自然返回false。提前返回当i已推进到len(s)即s全部匹配完成时立即返回true避免对t剩余部分做无谓遍历。这是将最差复杂度从必然扫完t优化为s匹配完成即终止的关键。s t两串完全相等时每个字符依次匹配成功最后一次匹配后i len(s)提前返回true符合删除 0 个字符即得到子序列的定义。结合仓库源码可运行测试验证本仓库在 selected_coding_interview/codes 目录下为本题提供了完整的可运行代码与驱动测试lc_392_is_subsequence.pyPython 实现附带了内置测试用例取s abc、t ahbgdc期望输出为True通过Solution().isSubsequence(...)直接运行即可复现结果lc_392_is_subsequence.javaJava 版在main方法中同样以abc、ahbgdc为输入声明expected_output true并通过Solution slt new Solution()调用后打印结果验证逻辑与 Python 版保持一致lc_392_is_subsequence_s1.cppC 版以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贪心查找维护一个游标idx表示t中当前可用的最小匹配位置遍历s的每个字符c在pos[c]中二分查找第一个大于idx的下标p若找不到则说明匹配失败返回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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Book 题解：判断子序列（Is Subsequence）双指针贪心匹配的 Python / Java / C++ 实现
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 abct ahbgdc删除t中的h、g后得到abc且顺序保持不变因此返回true若s axct 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为例逐步模拟指针移动过程步骤指针i指向s指针j指向t字符比较动作1i0→aj0→a相等匹配成功i1、j12i1→bj1→h不等匹配失败仅j23i1→bj2→b相等匹配成功i2、j34i2→cj3→g不等匹配失败仅j45i2→cj4→d不等匹配失败仅j56i2→cj5→c相等匹配成功i3i len(s)提前返回true可以看到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非常长本解法也只需要一次完整遍历即可给出结论这在字符串匹配类问题中是最优的量级。边界情况与易错点结合原文档与实现细节有以下几个容易忽略的边界情况空串s必须直接返回true。若不加保护直接访问s[0]/s.charAt(0)/s[0]在部分语言中会抛出越界异常。s长度大于t由于s的所有字符都需要在t中按序找到当s比t还长时必然返回false。本算法无需显式判断该情况——循环结束后i一定未走完s自然返回false。提前返回当i已推进到len(s)即s全部匹配完成时立即返回true避免对t剩余部分做无谓遍历。这是将最差复杂度从必然扫完t优化为s匹配完成即终止的关键。s t两串完全相等时每个字符依次匹配成功最后一次匹配后i len(s)提前返回true符合删除 0 个字符即得到子序列的定义。结合仓库源码可运行测试验证本仓库在 selected_coding_interview/codes 目录下为本题提供了完整的可运行代码与驱动测试lc_392_is_subsequence.pyPython 实现附带了内置测试用例取s abc、t ahbgdc期望输出为True通过Solution().isSubsequence(...)直接运行即可复现结果lc_392_is_subsequence.javaJava 版在main方法中同样以abc、ahbgdc为输入声明expected_output true并通过Solution slt new Solution()调用后打印结果验证逻辑与 Python 版保持一致lc_392_is_subsequence_s1.cppC 版以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贪心查找维护一个游标idx表示t中当前可用的最小匹配位置遍历s的每个字符c在pos[c]中二分查找第一个大于idx的下标p若找不到则说明匹配失败返回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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考