文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载本文基于 InterviewGuide 仓库forthespada/InterviewGuide中的 392.判断子序列题解 整理成文。LeetCode 392 是一道高频且典型的字符串子序列判定问题给定字符串s和t判断s是否为t的子序列。它既考察双指针贪心的基本功又在后续挑战中引出预处理 二分查找这一应对海量查询的经典优化思路是校招与社招面试中性价比极高的一道题。读完本文你将掌握双指针贪心的 O(len(t)) 判定写法、其复杂度边界分析以及面向k 10 亿级别海量短串批量判定的字母位置索引 二分查找进阶方案并理解两种方案各自的适用场景与取舍。题目回顾子序列判定的本质题目要求给定字符串s和t判断s是否为t的子序列。题目对输入做了两个关键约束s和t中仅包含英文小写字母共 26 个字符这一点是后续挑战解法成立的前提字符串t可能会很长长度约500,000而s是短字符串长度 100。所谓子序列是指原始字符串删除一些也可以不删除字符、但不改变剩余字符相对位置所形成的新字符串。注意它不同于子串——子串要求连续子序列只要求保持相对顺序。两个示例示例 1s abct ahbgdc返回truea - b - c可以按序在t中匹配到示例 2s axct ahbgdc返回falsex之后找不到仍位于其后的c。而题目的后续挑战则把问题升级为批量场景如果有大量输入的S称作S1, S2, ... , Sk其中k 10 亿你需要依次检查它们是否为T的子序列。在这种情况下你会怎样改变代码这一个挑战题设正是面试官常用来考察候选人对只读一遍长文本、复用索引、加速多次查询这一思想的试金石。解法一双指针贪心一次扫描判定单个子序列思路指针只前进永不回退对于单次判定最朴素也最正确的思路是贪心用指针i遍历s的每个字符用指针j在t中从左向右寻找当前s[i]第一次出现的位置找到后两个指针同时前进一步继续匹配s的下一个字符。贪心在这里为什么正确因为对于按序匹配类问题在t中越早匹配到当前字符留给后续字符的剩余空间就越大绝不会因为提前匹配而错失更优解——提前匹配只会让后续匹配更容易不会更难。仓库原题解代码C以下为 InterviewGuide 仓库中给出的第一版实现采用while(true)内层循环在t中推进j寻找匹配bool isSubsequence(string s, string t) { int len t.size(), count 0; for (unsigned i 0, j 0; i s.size(); i) { while (true) { if (j len s[i] t[j]) { count; j; break; } else if (j len) j; else break; } if (j len i s.size() - 1) { return false; } } if (count s.size()) return true; else return false; }这份代码的执行表现原文档记录执行用时约52 ms在所有 C 提交中击败约83.51%的用户内存消耗约17.1 MB击败约21.38%的用户。对仓库版本的代码走读与边界分析逐行走读这份代码可以帮助我们理解其正确性关键与可以简化的地方外层循环i遍历s的每个字符j维护当前已扫描到的t的位置整个匹配过程中j单调递增、从不回退这正是贪心策略的体现。内层循环在t中从j开始向后找与s[i]相等的字符找到则count并j越过已匹配字符后break找不到j越界则直接break。提前返回若j已经走完tj len而s还有字符未匹配i s.size() - 1说明t已无剩余字符直接返回false。收尾判断以count是否等于s.size()作为最终结论。这段代码逻辑正确但有三点值得注意的冗余与边界隐患变量count与i实际上是同步增长的count恰好发生在每轮外层循环匹配成功一次时因此最终count s.size()的判断等价于s中每个字符都匹配成功count本身可以省略判断i s.size() - 1时i是unsigned类型当s.size() 0时s.size() - 1会回绕成一个极大的无符号数导致条件恒为真存在空串边界下的潜在隐患更稳妥的写法是直接判断j len时立即return false当s为空串时空串天然是任何串的子序列应在进入循环前单独处理或由count s.size()自然返回true内层while(true)完全可以压缩为if判断让代码更简洁。更简洁的等价写法双指针推荐双指针贪心的思路完全可以用更简洁、更不容易出错的方式表达bool isSubsequence(string s, string t) { if (s.empty()) return true; // 空串是任何字符串的子序列 int i 0; // i 指向 sj 指向 t for (int j 0; j t.size(); j) { if (i s.size() s[i] t[j]) { i; // 匹配成功s 指针前移 } if (i s.size()) return true; // s 全部匹配完 } return false; }这段代码的要点i指向s中下一个待匹配字符j扫描t每当t[j] s[i]i前进一位j每轮必然前进一位当i走到s.size()说明s中所有字符都已在t中按序找到返回true否则扫描完t后返回false。该写法将寻找、推进、边界判断融为一体s[i]的越界检查放在条件中天然规避了无符号数回绕问题是面试时更推荐的口述与编码版本。复杂度分析时间复杂度O(len(s) len(t))。i最多前进len(s)次j至多扫描len(t)次整体线性。在原题约束len(t) ~ 500,000len(s) 100下单次判定非常快空间复杂度O(1)只使用了常数个指针变量不随输入规模增长。双指针方案的适用边界单次查询很优秀海量查询不可行双指针方案对单次判定是最优的它只需读一遍t不产生任何额外结构。但一旦进入后续挑战场景——k 10 亿个S需要依次判定——双指针的劣势就暴露无遗每个S都要从头到尾或至少到匹配完成扫描一遍t总代价为O(k * len(t))即使按len(t) 500,000、k 10 亿估算总比较次数高达5 * 10^14量级显然无法接受更关键的是t中大量字符会在不同S的判定中被重复扫描这部分重复劳动完全可以提前消除。于是问题就转化为如何把扫描t变成查询t这正是解法二的核心思想。解法二预处理 二分查找把扫描变为查询核心思想为 26 个字母各建一张位置表题面明确s与t仅含英文小写字母共 26 种。预处理阶段我们只遍历t一次把每个字母在t中出现的位置下标按升序分别存入 26 个数组dp[0] - 字母 a 在 t 中出现的所有位置升序 dp[1] - 字母 b 在 t 中出现的所有位置升序 ... dp[25] - 字母 z 在 t 中出现的所有位置升序构建完成后判断s是否为t的子序列就变成对s中每个字符执行一次在对应位置表中二分查找大于当前匹配游标的最小下标的操作维护一个游标tag记录上一个字符在t中匹配到的位置对s的每个字符c在dp[c - a]中二分查找第一个大于tag的位置pos若找不到即c在t中tag之后已不存在则s不是t的子序列返回false若找到更新tag pos继续匹配下一个字符。由于每个S至多len(s) 100个字符而每个字符的二分查找在位置表上只需O(log n)次比较位置表长度为len(t) ~ 500,000log 约 19 次单个S的判定开销被压到了约100 * 19 ≈ 1900次比较的常量级与len(t)完全解耦。仓库原题解代码C以下为仓库中针对后续挑战给出的实现bool isSubsequence(string s, string t) { vectorvectorint dp(26); int tag -1; for (int i 0; i t.size(); i) dp[t[i] - a].push_back(i); // 预处理按字母归档 t 中所有下标 for (int i 0; i s.size(); i) { int now s[i] - a; // 当前待匹配字符 int left 0, right dp[now].size() - 1; while (left right) { // 二分查找第一个 tag 的位置 int mid (left right) / 2; if (dp[now][mid] tag) right mid; else left mid 1; } if (right left || dp[now][left] tag) return false; tag dp[now][left]; } return true; }对仓库版本的代码走读与边界分析这段代码值得逐行理解尤其是二分查找的边界处理预处理for (int i 0; i t.size(); i) dp[t[i] - a].push_back(i);一遍遍历把t中每个字符的下标归档到对应字母的vector天然升序。vectorvectorint dp(26)恰好对应 26 个英文小写字母游标初始化tag -1表示上一个匹配位置之前——因为t下标从 0 开始-1保证第一个字符可以从位置 0 起查二分查找在dp[now]升序数组中寻找第一个大于tag的元素。left/right分别指向查找区间两端若dp[now][mid] tag说明mid及其右侧都满足条件但可能有更靠左的满足者故收缩右边界right mid否则说明mid及其左侧都不满足 tag收缩左边界left mid 1循环结束后left指向第一个大于tag的位置。失败判定right left表示区间被收缩空说明dp[now]中不存在大于tag的位置dp[now][left] tag覆盖dp[now]为空right -1、left 0或全部位置均 tag的情形。两种情形都意味着该字符无法在t中按序找到返回false游标更新tag dp[now][left]把当前已匹配位置推进到本次查到的下标保证后续字符的查找起点只前进不回退。一个值得注意的细节当s为空串时外层循环不会执行函数直接走到return true——空串天然是t的子序列这里无需特判即可正确返回。另外若某个字符在t中完全不存在其dp[now]为空vectorright初始为-1二分循环不进入随后的dp[now][left] tag判断访问空数组下标 0在vector上属于未定义行为更稳妥的写法是先判断dp[now].empty()再进入二分。复杂度分析预处理阶段O(len(t))时间构建 26 张位置表空间O(len(t))单次判定阶段对s的每个字符做一次二分查找单字符O(log(len(t)))整体O(len(s) * log(len(t)))。在原题约束下len(s) 100len(t) ~ 500,000单个S的判定比较次数约为100 * log2(500000) ≈ 100 * 19 1900次与len(t)完全解耦海量场景总代价O(len(t) k * len(s) * log(len(t)))。预处理只做一次之后每个S都是常量级查询k从10 亿增长时总代价近似线性于k而非k * len(t)这正是它能支撑海量判定的根本原因。原文档对这段实现的复杂度总结为创建数组需要O(t.size())索引递增对s的单个字符使用二分查找20 次之内即可找到整体约为O(t.size() 2000)量级完全适用于大量输入的子序列判定。两种方案对比与面试答题要点对比维度双指针贪心预处理 二分查找单次判定时间复杂度O(len(s) len(t))O(len(s) * log(len(t)))海量判定总时间复杂度O(k * len(t))随k线性爆炸O(len(t) k * len(s) * log(len(t)))查询与len(t)解耦空间复杂度O(1)O(len(t))26 张位置表适用场景单次或少量判定大量万级、亿级以上短串批量判定实现复杂度低双指针即可中等需处理二分边界面试答题时建议按如下节奏组织思路先给出双指针贪心说明i指s、j指t匹配成功ij永不回退的正确性与O(len(s) len(t))复杂度主动引出后续挑战指出当k达到 10 亿量级时重复扫描t不可接受关键在于把扫描变成查询再给出预处理方案利用仅 26 个小写字母这一约束为每个字母建位置索引表用二分查找将单次判定降到O(len(s) * log(len(t)))补充边界细节如空串处理、dp[now]为空时的判断、tag游标的单调性。该预计算 二分查找的思想在仓库的姊妹题 792.匹配子序列的单词数 中有更直接的体现——该题要求对单词字典中大量单词统计是S子序列的个数仓库题解同样先为S构建unordered_mapchar, vectorint位置表再用upper_bound逐个单词二分推进匹配游标。两道题放在一起看恰好构成单查询与批量查询的完整对照值得一并研读。总结LeetCode 392 判断子序列是一个典型的一题两解、由浅入深的题目双指针贪心解决单次判定的最优解O(len(s) len(t))时间、O(1)空间代码极简是面试手写的第一选择预处理 二分查找解决后续挑战中的海量判定牺牲一次O(len(t))的预构建换来每个查询与t长度解耦的常量级开销是面试中展示工程思维与算法优化的加分项。两种方案并不是竞争关系而是同一道题在不同数据规模约束下的两种正确答案。能根据题目约束自主切换方案、并准确说明每种方案的复杂度和适用边界正是这道题作为高频面试题想要考察的核心能力。本文由 InterviewGuide 仓库中的 392.判断子序列题解 整理扩充而来更多二分查找系列题解可继续浏览 06-二分查找 目录。赞分享文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载相关推荐codeforces-go 算法模板库实战LeetCode 392 判断子序列的贪心匹配与子序列自动机codeforces go 算法模板库实战LeetCode 392 判断子序列的贪心匹配与子序列自动机 导读 本文以 LeetCode 392「判断子序列I科学计算AlgoNote 算法通关手册LeetCode 0392「判断子序列」——双指针贪心匹配的完整解析与代码实现AlgoNote 算法通关手册LeetCode 0392「判断子序列」——双指针贪心匹配的完整解析与代码实现 本文是「算法通关手册」 题目解析 https:/教程文档知识库InterviewGuide 算法精讲LeetCode 167 两数之和 II——有序数组下的二分边界陷阱与双指针解法InterviewGuide 算法精讲LeetCode 167 两数之和 II——有序数组下的二分边界陷阱与双指针解法 导读 本篇是 InterviewGui文档教程知识库上一篇Midscene Chrome 扩展自然语言操控浏览器5 分钟跑通首次运行下一篇PVCNN 源码深度剖析核心模块 PVConv 实现原理与代码解读创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考