1. 项目概述从一道题看华为OD机试的深度与广度最近在帮几个准备华为OD机试的朋友做模拟练习他们不约而同地都问到了一类题目字符串子序列相关的问题。这类题在机试中出现的频率相当高尤其是像“字符串子序列II”这种带点变体的题目几乎成了检验候选人基础算法能力和思维严谨度的“试金石”。我自己当年准备面试时也在这类题目上花了不少功夫因为它看似简单——不就是判断一个字符串是不是另一个字符串的子序列吗但一旦加上各种限制条件比如本题中的“II”往往就意味着有额外的约束比如顺序、间隔、甚至是特定字符的匹配规则复杂度一下子就上来了。这道“字符串子序列II”的真题其核心价值在于它完美地串联起了字符串处理、双指针或动态规划算法思想以及细致的边界条件处理。对于正在备战华为OD尤其是目标岗位对C、Java、Python等编程能力有要求的同学来说吃透这道题收获的远不止一个ACAccepted的代码。它能帮你建立起处理序列匹配类问题的通用思维框架无论是面试中的白板编程还是实际工作中遇到类似的数据流匹配、日志分析、模式检测等场景这套思路都能直接复用。我打算结合这道题把它的解题思路、代码实现涵盖C、Java、Python、C语言和JS、以及其中容易踩坑的细节掰开揉碎了讲清楚。你会发现一道好的机试题就像一份精心设计的需求文档读懂题目背后的意图往往比写出能跑的代码更重要。2. 核心需求解析什么是“字符串子序列II”在开始写代码之前我们必须百分百明确题目到底要我们做什么。很多同学机试丢分不是算法不会而是题目没审清。“字符串子序列II”这个标题我们可以拆解成两个部分来理解。首先是“子序列”的基本定义。这是本题的基石。给定两个字符串s和t我们说s是t的子序列意味着可以通过删除t中的一些字符也可以不删除使得剩下的字符按原始顺序连接起来恰好等于s。这里的关键词是“原始顺序”。例如s “abc”t “ahbgdc”那么s是t的子序列因为我们可以从t中找到字符 ‘a’, ‘b’, ‘c’并且它们在t中的出现顺序和s中的顺序一致。即使t中间夹杂了 ‘h’, ‘g’, ‘d’ 也没关系。其次是“II”所代表的变体或额外条件。这是本题的难点和考点所在。在经典的子序列判断问题LeetCode 392. 判断子序列中通常只要求判断s是否是t的子序列。但华为OD的题目往往会在基础上增加一层约束。根据常见的出题模式“II”可能指代以下几种情况之一我们需要根据具体的题目描述来确定这里假设一种常见且经典的变体最短匹配窗口不仅要判断s是否是t的子序列还要找出t中匹配s的最短连续子串注意这里变成了“子串”要求连续。这实际上变成了一个滑动窗口问题。带有特定距离限制匹配时s中相邻两个字符在t中出现的下标距离不能超过某个值K。这增加了对匹配“紧凑度”的要求。每个字符只能使用一次这是最常见的一种“II”变体也是本文重点讨论的。题目通常会这样描述给定字符串s和t判断能否从t中按顺序挑出不相交的、长度与s相同的子序列。或者说t中的每个字符最多只能被使用一次来匹配s。这听起来和基础定义一样其实不然。在基础定义中我们只关心顺序不关心t中的字符是否被重复使用。例如s “aab”t “aaab”。在基础定义下s是t的子序列取前两个’a’和最后的’b’。但在“每个字符只能用一次”的规则下s可能就不是t的子序列了因为我们需要两个 ‘a’ 和一个 ‘b’且不能重复使用字符。t中有三个 ‘a’ 一个 ‘b’看似够用但关键在于匹配时必须按顺序、不重复地占用。我们可以用前两个 ‘a’ 和那个 ‘b’ 来匹配所以这个例子下仍然是子序列。但如果s “aaa”t “aa”那无论如何都无法匹配了。为了本文讨论的聚焦我们假设“字符串子序列II”指的是这个经典变体判断字符串s是否是字符串t的子序列其中t中的每个字符最多只能被使用一次来按顺序匹配s中的字符。这实际上是LeetCode 392题的标准解法所隐含的条件也是面试中最常考的形式。它的核心需求可以归纳为设计一个算法高效地检查较短的字符串s能否被较长的字符串t在“一对一、保顺序”的前提下完全容纳。注意在实际考试中务必仔细阅读题目输入输出描述和示例。这里的解析是基于常见考点的合理推测。如果题目有特殊说明如最短长度、特定代价算法需要相应调整。3. 算法思路深度剖析双指针的巧妙运用明确了需求后我们来看解决方案。对于这个变体最优雅且高效的思路是双指针法。它的时间复杂度是 O(nm)其中 n 和 m 分别是t和s的长度空间复杂度是 O(1)几乎是最优解。3.1 算法核心思想我们可以想象有两个“指针”或“索引”一个指向字符串s的当前待匹配字符记为i另一个指向字符串t的当前待检查字符记为j。算法的过程就是让指针j在t上一步步向后移动试图为s[i]找到匹配项。初始化i 0,j 0。分别指向s和t的开头。匹配过程如果s[i] t[j]说明我们在t中为s的第i个字符找到了一个匹配。那么i和j都可以向后移动一位i,j准备匹配s的下一个字符。这意味着t[j]这个字符被“消耗”掉了用于匹配s[i]。如果s[i] ! t[j]说明t[j]这个字符无法匹配当前的s[i]。根据子序列的定义我们可以选择“删除”t中的这个字符即忽略它。在算法上我们只需要将j向后移动一位j继续用下一个t中的字符来尝试匹配当前的s[i]。终止条件成功当i移动到了s的末尾即i len(s)说明我们已经为s中的所有字符都在t中按顺序找到了匹配。此时返回true。失败如果j先移动到了t的末尾j len(t)而i还没有到s的末尾这意味着我们已经遍历完了整个t仍然没有为s中剩余的所有字符找到足够的匹配。此时返回false。3.2 为什么双指针法是有效的这个算法的正确性基于贪心思想为了匹配s中的当前字符s[i]我们总是在t中从当前位置j开始寻找第一个与之相等的字符。这个“第一个”的选择是最优的因为它为s中后续字符的匹配留下了尽可能多的t的剩余部分。如果放弃这个第一个可匹配的字符去使用后面更远的相同字符并不会让匹配更容易成功反而可能因为消耗了中间本可用于匹配其他字符的位置而导致失败。3.3 与动态规划解法的对比有些同学可能会想到用动态规划DP比如定义一个dp[i][j]表示s的前i个字符是否是t的前j个字符的子序列。状态转移方程也清晰。但DP解法的时间复杂度是 O(nm)空间复杂度至少是 O(nm)优化后可达 O(m)。在机试这种对时间和空间都有严格限制的场景下双指针的 O(nm) 线性解法无疑是更优的选择。DP解法更适合处理更复杂的子序列问题比如带有权值、需要计数、或者“II”代表其他复杂约束的情况。实操心得在华为OD机试中遇到单纯的子序列判断首选双指针。它代码简洁运行高效不容易出错。一定要把这种基础算法的模板记熟达到能闭着眼睛写出来的程度为解决更复杂的问题节省时间和脑力。4. 多语言代码实现与细节分析理解了算法接下来就是落地到代码。不同语言在实现时有其各自的语法特点和注意事项。我会用C、Java、Python、C语言和JavaScript五种语言分别实现并指出其中的关键点。4.1 C 实现C的实现追求高效和简洁。利用下标或迭代器都能清晰表达双指针的思想。#include iostream #include string using namespace std; bool isSubsequence(const string s, const string t) { int i 0, j 0; // i指向s j指向t int s_len s.length(), t_len t.length(); while (i s_len j t_len) { if (s[i] t[j]) { // 匹配成功同时移动两个指针 i; } // 无论是否匹配t的指针j都要向后移动 // 匹配成功时j已经指向了被使用的字符下一次循环自然从下一位开始 // 匹配失败时j需要继续后移寻找匹配 j; } // 循环结束后如果s的所有字符都匹配完了(i s_len)则是子序列 return i s_len; } int main() { string s, t; // 假设输入格式为两行分别代表s和t // cin s t; // 这种方式遇到带空格的字符串会出问题 getline(cin, s); getline(cin, t); if (isSubsequence(s, t)) { cout true endl; } else { cout false endl; } return 0; }C实现要点参数传递使用const string传递字符串避免不必要的拷贝。循环条件while (i s_len j t_len)确保了只要有一个字符串遍历完就退出循环。指针移动逻辑这是最核心也最容易糊涂的地方。注意无论是否匹配j都必须递增。匹配时i和j都指向了匹配成功的字符j是为了在下一轮循环中检查t的下一个字符。我们可以把j写在循环末尾逻辑更统一。上面代码把j放在了if外面效果相同。输入处理机试中要特别注意输入格式。如果字符串可能包含空格一定要用getline(cin, str)而不是cin str。4.2 Java 实现Java的实现风格类似利用charAt()方法进行字符访问。import java.util.Scanner; public class Main { public static boolean isSubsequence(String s, String t) { int i 0, j 0; int sLen s.length(), tLen t.length(); while (i sLen j tLen) { if (s.charAt(i) t.charAt(j)) { i; // 匹配成功移动s的指针 } j; // 无论是否匹配t的指针都要移动 } return i sLen; // 如果s的所有字符都匹配完了则是子序列 } public static void main(String[] args) { Scanner scanner new Scanner(System.in); // 假设输入为两行 String s scanner.nextLine(); String t scanner.nextLine(); scanner.close(); System.out.println(isSubsequence(s, t)); } }Java实现要点字符串访问在循环中频繁调用charAt()是常规操作对于机试长度的字符串性能完全足够。资源管理使用了Scanner读取输入记得在最后调用close()方法虽然在程序结束时也会释放但养成好习惯。返回值直接返回boolean类型在main中输出对应的字符串。4.3 Python 实现Python的代码最为简洁可以利用其强大的迭代特性。def is_subsequence(s: str, t: str) - bool: i, j 0, 0 s_len, t_len len(s), len(t) while i s_len and j t_len: if s[i] t[j]: i 1 j 1 return i s_len if __name__ __main__: s input().strip() t input().strip() print(is_subsequence(s, t))更Pythonic的写法利用迭代器def is_subsequence_pythonic(s: str, t: str) - bool: it iter(t) # 将t转换为一个迭代器 # all()函数会检查可迭代对象中的所有元素是否为真 # (c in it) 这个表达式会从迭代器it中消耗字符直到找到等于c的字符。 # 如果对于s中的每个字符c都能在it的剩余部分中找到则返回True。 return all(c in it for c in s)Python实现要点简洁性基础写法和C/Java类似非常直观。Pythonic写法all(c in it for c in s)这行代码是Python的精华。iter(t)创建了一个迭代器c in it会从迭代器中逐个取出元素与c比较直到找到匹配项或迭代器耗尽。这种方法同样隐式地实现了“每个字符只用一次”和“顺序匹配”的规则且代码极其简短。在机试中如果对Python语法非常熟悉用这种写法能节省大量时间。类型提示def is_subsequence(s: str, t: str) - bool:增加了代码的可读性虽然不是强制要求。4.4 C语言 实现C语言需要手动处理字符串数组更接近底层。#include stdio.h #include stdbool.h // 为了使用bool类型 #include string.h bool isSubsequence(char* s, char* t) { int i 0, j 0; // 假设s和t都是以\0结尾的字符串 while (s[i] ! \0 t[j] ! \0) { if (s[i] t[j]) { i; } j; } // 如果s已经到达末尾(\0)说明全部匹配成功 return s[i] \0; } int main() { char s[1000], t[1000]; // 根据题目可能的最大长度调整数组大小 // 使用fgets读取一行包括可能的空格并去除末尾的换行符 fgets(s, sizeof(s), stdin); s[strcspn(s, \n)] \0; // 去除换行符 fgets(t, sizeof(t), stdin); t[strcspn(t, \n)] \0; if (isSubsequence(s, t)) { printf(true\n); } else { printf(false\n); } return 0; }C语言实现要点字符串结束符循环条件s[i] ! ‘\0‘是判断字符串是否结束的标准方法。输入处理fgets会读取换行符所以要用strcspn或手动替换来去除它这是C语言处理输入时一个非常常见的坑。数组大小必须预先分配足够大的字符数组。在机试中要仔细看题目给出的数据范围确保数组不会越界。布尔类型C99标准支持_Bool和stdbool.h中的bool使代码更清晰。4.5 JavaScript (Node.js) 实现对于前端或JS方向的考生用Node.js环境解题是常态。const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); function isSubsequence(s, t) { let i 0, j 0; while (i s.length j t.length) { if (s[i] t[j]) { i; } j; } return i s.length; } // 处理多行输入 let inputLines []; rl.on(line, (line) { inputLines.push(line.trim()); if (inputLines.length 2) { // 假设输入为两行 const s inputLines[0]; const t inputLines[1]; console.log(isSubsequence(s, t)); rl.close(); } }).on(close, () { process.exit(0); });JavaScript实现要点输入输出这是Node.js机试中最麻烦的部分之一。必须使用readline模块来逐行读取输入。上面的代码是一个通用的处理两行输入的模板。算法逻辑和之前其他语言完全一致。在线判题系统有些OJ可能直接要求实现一个函数比如function isSubsequence(s, t)而不需要处理输入输出。务必看清题目要求。5. 边界条件与常见错误排查即使算法思路清晰代码写出来也可能因为边界条件处理不当而丢分。下面我总结了几类常见的“坑”。5.1 空字符串处理场景s是空字符串“”。正确逻辑空字符串应该是任何字符串的子序列因为通过删除所有字符可以得到空串。在我们的双指针算法中i初始为0s_len为0while循环条件i s_len立即为假循环不会执行直接返回i s_len即0 0结果为true。所以我们的算法天然正确处理了这种情况。检查点不需要特殊处理但心里要清楚这是正确的。5.2s比t长场景len(s) len(t)。正确逻辑显然s不可能是t的子序列。我们的算法也能正确处理j指针会先走到t的末尾此时i必然小于s_len循环结束返回false。检查点算法虽然能处理但在某些实现中如果先进行长度判断if (len(s) len(t)) return false;可以提前终止起到微小的优化作用但非必需。5.3 输入字符串包含空格场景题目说字符串由“字母和空格”组成。错误做法使用cin s或scanf(“%s”, s)这类函数会以空格为分隔符导致只能读入第一个单词。正确做法使用能读取整行的函数如 C 的getline(cin, s) C 的fgets(s, sizeof(s), stdin) Python 的input() Java 的scanner.nextLine()。这是机试中非常高发的错误5.4 大小写敏感问题场景题目描述中是否明确“区分大小写”通常默认是区分的。处理我们的比较s[i] t[j]是区分大小写的。如果题目要求不区分需要在比较前统一转换为大写或小写例如tolower(s[i]) tolower(t[j])。5.5 指针移动逻辑混淆错误写法while (i s_len j t_len) { if (s[i] t[j]) { i; j; // 只在匹配时移动j } // 忘记了在不匹配时移动j导致死循环 }或者while (i s_len j t_len) { if (s[i] t[j]) { i; } // j 放在了else里导致匹配成功后j不移动下一轮还是和同一个t[j]比较逻辑错误。 else { j; } }正确理解j指针必须每轮循环无条件地后移一位因为它代表我们正在检查t中的当前字符。无论这个字符是否匹配s[i]检查过后我们都应该看下一个字符。5.6 多组数据输入场景题目可能要求处理多组测试用例直到文件结束。处理需要将核心判断逻辑包装成函数在主循环中不断读取s和t。例如在C中string s, t; while (getline(cin, s) getline(cin, t)) { // 确保能读到两个字符串 cout (isSubsequence(s, t) ? “true” : “false”) endl; }在Python中import sys for line in sys.stdin: s line.strip() t sys.stdin.readline().strip() # 注意要再读一行作为t if not t: # 处理可能的文件末尾异常 break print(is_subsequence(s, t))6. 性能优化与进阶思考对于这道题双指针的 O(nm) 解法已经是最优。但在一些更复杂的变体或者面试官追问的情况下我们可以进行一些拓展思考。6.1 如果需要对同一个s检查多个不同的t这是LeetCode上的一道后续题目。如果有一个很短的字符串s和一大堆非常长的字符串t1, t2, …, tk我们需要对每个t都判断s是否是它的子序列。如果对每个t都做一次 O(|t|) 的双指针扫描总时间复杂度是 O(k * |t|_avg)如果k很大效率可能不高。优化思路预处理s。但s通常很短预处理意义不大。更常见的优化是预处理t。我们可以为t构建一个“字符跳转表”。例如对于t “ahbgdc”我们构建一个数组next_pos[i][ch]表示从位置i开始下一个字符ch出现的位置。这样在匹配s时我们可以用 O(|s|) 的时间完成因为每次查找下一个匹配字符是 O(1) 的。构建这个表需要 O(26 * |t|) 的时间假设只有小写字母。这在k很大且每个t自身也很长时能显著提升效率。不过在标准的单次查询机试题中不需要这么复杂。6.2 如果“II”代表其他含义如前所述如果“II”代表寻找最短匹配子串那么算法就需要改变。这通常使用滑动窗口或二分查找来解决。滑动窗口维护一个窗口[left, right]在t上滑动。用一个哈希表或数组need记录s中每个字符需要的数量用另一个window记录当前窗口中各字符的数量。移动right扩大窗口直到覆盖了所有s的字符然后移动left收缩窗口以找到最短的满足条件的子串。这本质上是最小覆盖子串问题的简化版因为这里只要求字符按顺序出现而非连续出现所有字符所以更复杂一些可能需要结合双指针和队列。二分查找如果t非常长且需要多次查询不同的s可以预处理t记录每个字母出现的所有位置索引列表是有序的。对于s中的每个字符我们在这个字符的位置列表中二分查找大于上一个匹配位置的最小索引。如果找不到则失败。这种方法每次查询的时间复杂度是 O(|s| * log|t|)。6.3 机试中的实战技巧先写思路注释在代码编辑器里先花1-2分钟用注释写下算法步骤。这能帮你理清思路避免写到一半逻辑混乱。使用清晰的变量名i_s,i_t比i,j更清晰sIndex,tIndex也不错。写完立刻测试边界在脑子里或草稿上跑一下空串、单字符、s更长等边界情况。利用本地IDE调试如果环境允许将样例输入复制到本地提前写好的代码中运行确保输出格式完全一致比如大小写、是否换行。时间管理这道题属于简单/中等难度目标是在15-20分钟内完成读题、构思、编码、测试。如果卡壳超过10分钟考虑是不是理解错了题意。这道“字符串子序列II”题目就像一把钥匙打开的是解决字符串匹配类问题的大门。掌握其核心的双指针思想并能根据“II”代表的不同约束灵活变通你在华为OD机试乃至后续的技术面试中遇到类似的题目就能从容应对。编程能力的提升没有捷径就是通过这样一道道经典题目的深入思考和反复练习把别人的思路内化成自己的肌肉记忆。
1. 项目概述从一道题看华为OD机试的深度与广度最近在帮几个准备华为OD机试的朋友做模拟练习他们不约而同地都问到了一类题目字符串子序列相关的问题。这类题在机试中出现的频率相当高尤其是像“字符串子序列II”这种带点变体的题目几乎成了检验候选人基础算法能力和思维严谨度的“试金石”。我自己当年准备面试时也在这类题目上花了不少功夫因为它看似简单——不就是判断一个字符串是不是另一个字符串的子序列吗但一旦加上各种限制条件比如本题中的“II”往往就意味着有额外的约束比如顺序、间隔、甚至是特定字符的匹配规则复杂度一下子就上来了。这道“字符串子序列II”的真题其核心价值在于它完美地串联起了字符串处理、双指针或动态规划算法思想以及细致的边界条件处理。对于正在备战华为OD尤其是目标岗位对C、Java、Python等编程能力有要求的同学来说吃透这道题收获的远不止一个ACAccepted的代码。它能帮你建立起处理序列匹配类问题的通用思维框架无论是面试中的白板编程还是实际工作中遇到类似的数据流匹配、日志分析、模式检测等场景这套思路都能直接复用。我打算结合这道题把它的解题思路、代码实现涵盖C、Java、Python、C语言和JS、以及其中容易踩坑的细节掰开揉碎了讲清楚。你会发现一道好的机试题就像一份精心设计的需求文档读懂题目背后的意图往往比写出能跑的代码更重要。2. 核心需求解析什么是“字符串子序列II”在开始写代码之前我们必须百分百明确题目到底要我们做什么。很多同学机试丢分不是算法不会而是题目没审清。“字符串子序列II”这个标题我们可以拆解成两个部分来理解。首先是“子序列”的基本定义。这是本题的基石。给定两个字符串s和t我们说s是t的子序列意味着可以通过删除t中的一些字符也可以不删除使得剩下的字符按原始顺序连接起来恰好等于s。这里的关键词是“原始顺序”。例如s “abc”t “ahbgdc”那么s是t的子序列因为我们可以从t中找到字符 ‘a’, ‘b’, ‘c’并且它们在t中的出现顺序和s中的顺序一致。即使t中间夹杂了 ‘h’, ‘g’, ‘d’ 也没关系。其次是“II”所代表的变体或额外条件。这是本题的难点和考点所在。在经典的子序列判断问题LeetCode 392. 判断子序列中通常只要求判断s是否是t的子序列。但华为OD的题目往往会在基础上增加一层约束。根据常见的出题模式“II”可能指代以下几种情况之一我们需要根据具体的题目描述来确定这里假设一种常见且经典的变体最短匹配窗口不仅要判断s是否是t的子序列还要找出t中匹配s的最短连续子串注意这里变成了“子串”要求连续。这实际上变成了一个滑动窗口问题。带有特定距离限制匹配时s中相邻两个字符在t中出现的下标距离不能超过某个值K。这增加了对匹配“紧凑度”的要求。每个字符只能使用一次这是最常见的一种“II”变体也是本文重点讨论的。题目通常会这样描述给定字符串s和t判断能否从t中按顺序挑出不相交的、长度与s相同的子序列。或者说t中的每个字符最多只能被使用一次来匹配s。这听起来和基础定义一样其实不然。在基础定义中我们只关心顺序不关心t中的字符是否被重复使用。例如s “aab”t “aaab”。在基础定义下s是t的子序列取前两个’a’和最后的’b’。但在“每个字符只能用一次”的规则下s可能就不是t的子序列了因为我们需要两个 ‘a’ 和一个 ‘b’且不能重复使用字符。t中有三个 ‘a’ 一个 ‘b’看似够用但关键在于匹配时必须按顺序、不重复地占用。我们可以用前两个 ‘a’ 和那个 ‘b’ 来匹配所以这个例子下仍然是子序列。但如果s “aaa”t “aa”那无论如何都无法匹配了。为了本文讨论的聚焦我们假设“字符串子序列II”指的是这个经典变体判断字符串s是否是字符串t的子序列其中t中的每个字符最多只能被使用一次来按顺序匹配s中的字符。这实际上是LeetCode 392题的标准解法所隐含的条件也是面试中最常考的形式。它的核心需求可以归纳为设计一个算法高效地检查较短的字符串s能否被较长的字符串t在“一对一、保顺序”的前提下完全容纳。注意在实际考试中务必仔细阅读题目输入输出描述和示例。这里的解析是基于常见考点的合理推测。如果题目有特殊说明如最短长度、特定代价算法需要相应调整。3. 算法思路深度剖析双指针的巧妙运用明确了需求后我们来看解决方案。对于这个变体最优雅且高效的思路是双指针法。它的时间复杂度是 O(nm)其中 n 和 m 分别是t和s的长度空间复杂度是 O(1)几乎是最优解。3.1 算法核心思想我们可以想象有两个“指针”或“索引”一个指向字符串s的当前待匹配字符记为i另一个指向字符串t的当前待检查字符记为j。算法的过程就是让指针j在t上一步步向后移动试图为s[i]找到匹配项。初始化i 0,j 0。分别指向s和t的开头。匹配过程如果s[i] t[j]说明我们在t中为s的第i个字符找到了一个匹配。那么i和j都可以向后移动一位i,j准备匹配s的下一个字符。这意味着t[j]这个字符被“消耗”掉了用于匹配s[i]。如果s[i] ! t[j]说明t[j]这个字符无法匹配当前的s[i]。根据子序列的定义我们可以选择“删除”t中的这个字符即忽略它。在算法上我们只需要将j向后移动一位j继续用下一个t中的字符来尝试匹配当前的s[i]。终止条件成功当i移动到了s的末尾即i len(s)说明我们已经为s中的所有字符都在t中按顺序找到了匹配。此时返回true。失败如果j先移动到了t的末尾j len(t)而i还没有到s的末尾这意味着我们已经遍历完了整个t仍然没有为s中剩余的所有字符找到足够的匹配。此时返回false。3.2 为什么双指针法是有效的这个算法的正确性基于贪心思想为了匹配s中的当前字符s[i]我们总是在t中从当前位置j开始寻找第一个与之相等的字符。这个“第一个”的选择是最优的因为它为s中后续字符的匹配留下了尽可能多的t的剩余部分。如果放弃这个第一个可匹配的字符去使用后面更远的相同字符并不会让匹配更容易成功反而可能因为消耗了中间本可用于匹配其他字符的位置而导致失败。3.3 与动态规划解法的对比有些同学可能会想到用动态规划DP比如定义一个dp[i][j]表示s的前i个字符是否是t的前j个字符的子序列。状态转移方程也清晰。但DP解法的时间复杂度是 O(nm)空间复杂度至少是 O(nm)优化后可达 O(m)。在机试这种对时间和空间都有严格限制的场景下双指针的 O(nm) 线性解法无疑是更优的选择。DP解法更适合处理更复杂的子序列问题比如带有权值、需要计数、或者“II”代表其他复杂约束的情况。实操心得在华为OD机试中遇到单纯的子序列判断首选双指针。它代码简洁运行高效不容易出错。一定要把这种基础算法的模板记熟达到能闭着眼睛写出来的程度为解决更复杂的问题节省时间和脑力。4. 多语言代码实现与细节分析理解了算法接下来就是落地到代码。不同语言在实现时有其各自的语法特点和注意事项。我会用C、Java、Python、C语言和JavaScript五种语言分别实现并指出其中的关键点。4.1 C 实现C的实现追求高效和简洁。利用下标或迭代器都能清晰表达双指针的思想。#include iostream #include string using namespace std; bool isSubsequence(const string s, const string t) { int i 0, j 0; // i指向s j指向t int s_len s.length(), t_len t.length(); while (i s_len j t_len) { if (s[i] t[j]) { // 匹配成功同时移动两个指针 i; } // 无论是否匹配t的指针j都要向后移动 // 匹配成功时j已经指向了被使用的字符下一次循环自然从下一位开始 // 匹配失败时j需要继续后移寻找匹配 j; } // 循环结束后如果s的所有字符都匹配完了(i s_len)则是子序列 return i s_len; } int main() { string s, t; // 假设输入格式为两行分别代表s和t // cin s t; // 这种方式遇到带空格的字符串会出问题 getline(cin, s); getline(cin, t); if (isSubsequence(s, t)) { cout true endl; } else { cout false endl; } return 0; }C实现要点参数传递使用const string传递字符串避免不必要的拷贝。循环条件while (i s_len j t_len)确保了只要有一个字符串遍历完就退出循环。指针移动逻辑这是最核心也最容易糊涂的地方。注意无论是否匹配j都必须递增。匹配时i和j都指向了匹配成功的字符j是为了在下一轮循环中检查t的下一个字符。我们可以把j写在循环末尾逻辑更统一。上面代码把j放在了if外面效果相同。输入处理机试中要特别注意输入格式。如果字符串可能包含空格一定要用getline(cin, str)而不是cin str。4.2 Java 实现Java的实现风格类似利用charAt()方法进行字符访问。import java.util.Scanner; public class Main { public static boolean isSubsequence(String s, String t) { int i 0, j 0; int sLen s.length(), tLen t.length(); while (i sLen j tLen) { if (s.charAt(i) t.charAt(j)) { i; // 匹配成功移动s的指针 } j; // 无论是否匹配t的指针都要移动 } return i sLen; // 如果s的所有字符都匹配完了则是子序列 } public static void main(String[] args) { Scanner scanner new Scanner(System.in); // 假设输入为两行 String s scanner.nextLine(); String t scanner.nextLine(); scanner.close(); System.out.println(isSubsequence(s, t)); } }Java实现要点字符串访问在循环中频繁调用charAt()是常规操作对于机试长度的字符串性能完全足够。资源管理使用了Scanner读取输入记得在最后调用close()方法虽然在程序结束时也会释放但养成好习惯。返回值直接返回boolean类型在main中输出对应的字符串。4.3 Python 实现Python的代码最为简洁可以利用其强大的迭代特性。def is_subsequence(s: str, t: str) - bool: i, j 0, 0 s_len, t_len len(s), len(t) while i s_len and j t_len: if s[i] t[j]: i 1 j 1 return i s_len if __name__ __main__: s input().strip() t input().strip() print(is_subsequence(s, t))更Pythonic的写法利用迭代器def is_subsequence_pythonic(s: str, t: str) - bool: it iter(t) # 将t转换为一个迭代器 # all()函数会检查可迭代对象中的所有元素是否为真 # (c in it) 这个表达式会从迭代器it中消耗字符直到找到等于c的字符。 # 如果对于s中的每个字符c都能在it的剩余部分中找到则返回True。 return all(c in it for c in s)Python实现要点简洁性基础写法和C/Java类似非常直观。Pythonic写法all(c in it for c in s)这行代码是Python的精华。iter(t)创建了一个迭代器c in it会从迭代器中逐个取出元素与c比较直到找到匹配项或迭代器耗尽。这种方法同样隐式地实现了“每个字符只用一次”和“顺序匹配”的规则且代码极其简短。在机试中如果对Python语法非常熟悉用这种写法能节省大量时间。类型提示def is_subsequence(s: str, t: str) - bool:增加了代码的可读性虽然不是强制要求。4.4 C语言 实现C语言需要手动处理字符串数组更接近底层。#include stdio.h #include stdbool.h // 为了使用bool类型 #include string.h bool isSubsequence(char* s, char* t) { int i 0, j 0; // 假设s和t都是以\0结尾的字符串 while (s[i] ! \0 t[j] ! \0) { if (s[i] t[j]) { i; } j; } // 如果s已经到达末尾(\0)说明全部匹配成功 return s[i] \0; } int main() { char s[1000], t[1000]; // 根据题目可能的最大长度调整数组大小 // 使用fgets读取一行包括可能的空格并去除末尾的换行符 fgets(s, sizeof(s), stdin); s[strcspn(s, \n)] \0; // 去除换行符 fgets(t, sizeof(t), stdin); t[strcspn(t, \n)] \0; if (isSubsequence(s, t)) { printf(true\n); } else { printf(false\n); } return 0; }C语言实现要点字符串结束符循环条件s[i] ! ‘\0‘是判断字符串是否结束的标准方法。输入处理fgets会读取换行符所以要用strcspn或手动替换来去除它这是C语言处理输入时一个非常常见的坑。数组大小必须预先分配足够大的字符数组。在机试中要仔细看题目给出的数据范围确保数组不会越界。布尔类型C99标准支持_Bool和stdbool.h中的bool使代码更清晰。4.5 JavaScript (Node.js) 实现对于前端或JS方向的考生用Node.js环境解题是常态。const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); function isSubsequence(s, t) { let i 0, j 0; while (i s.length j t.length) { if (s[i] t[j]) { i; } j; } return i s.length; } // 处理多行输入 let inputLines []; rl.on(line, (line) { inputLines.push(line.trim()); if (inputLines.length 2) { // 假设输入为两行 const s inputLines[0]; const t inputLines[1]; console.log(isSubsequence(s, t)); rl.close(); } }).on(close, () { process.exit(0); });JavaScript实现要点输入输出这是Node.js机试中最麻烦的部分之一。必须使用readline模块来逐行读取输入。上面的代码是一个通用的处理两行输入的模板。算法逻辑和之前其他语言完全一致。在线判题系统有些OJ可能直接要求实现一个函数比如function isSubsequence(s, t)而不需要处理输入输出。务必看清题目要求。5. 边界条件与常见错误排查即使算法思路清晰代码写出来也可能因为边界条件处理不当而丢分。下面我总结了几类常见的“坑”。5.1 空字符串处理场景s是空字符串“”。正确逻辑空字符串应该是任何字符串的子序列因为通过删除所有字符可以得到空串。在我们的双指针算法中i初始为0s_len为0while循环条件i s_len立即为假循环不会执行直接返回i s_len即0 0结果为true。所以我们的算法天然正确处理了这种情况。检查点不需要特殊处理但心里要清楚这是正确的。5.2s比t长场景len(s) len(t)。正确逻辑显然s不可能是t的子序列。我们的算法也能正确处理j指针会先走到t的末尾此时i必然小于s_len循环结束返回false。检查点算法虽然能处理但在某些实现中如果先进行长度判断if (len(s) len(t)) return false;可以提前终止起到微小的优化作用但非必需。5.3 输入字符串包含空格场景题目说字符串由“字母和空格”组成。错误做法使用cin s或scanf(“%s”, s)这类函数会以空格为分隔符导致只能读入第一个单词。正确做法使用能读取整行的函数如 C 的getline(cin, s) C 的fgets(s, sizeof(s), stdin) Python 的input() Java 的scanner.nextLine()。这是机试中非常高发的错误5.4 大小写敏感问题场景题目描述中是否明确“区分大小写”通常默认是区分的。处理我们的比较s[i] t[j]是区分大小写的。如果题目要求不区分需要在比较前统一转换为大写或小写例如tolower(s[i]) tolower(t[j])。5.5 指针移动逻辑混淆错误写法while (i s_len j t_len) { if (s[i] t[j]) { i; j; // 只在匹配时移动j } // 忘记了在不匹配时移动j导致死循环 }或者while (i s_len j t_len) { if (s[i] t[j]) { i; } // j 放在了else里导致匹配成功后j不移动下一轮还是和同一个t[j]比较逻辑错误。 else { j; } }正确理解j指针必须每轮循环无条件地后移一位因为它代表我们正在检查t中的当前字符。无论这个字符是否匹配s[i]检查过后我们都应该看下一个字符。5.6 多组数据输入场景题目可能要求处理多组测试用例直到文件结束。处理需要将核心判断逻辑包装成函数在主循环中不断读取s和t。例如在C中string s, t; while (getline(cin, s) getline(cin, t)) { // 确保能读到两个字符串 cout (isSubsequence(s, t) ? “true” : “false”) endl; }在Python中import sys for line in sys.stdin: s line.strip() t sys.stdin.readline().strip() # 注意要再读一行作为t if not t: # 处理可能的文件末尾异常 break print(is_subsequence(s, t))6. 性能优化与进阶思考对于这道题双指针的 O(nm) 解法已经是最优。但在一些更复杂的变体或者面试官追问的情况下我们可以进行一些拓展思考。6.1 如果需要对同一个s检查多个不同的t这是LeetCode上的一道后续题目。如果有一个很短的字符串s和一大堆非常长的字符串t1, t2, …, tk我们需要对每个t都判断s是否是它的子序列。如果对每个t都做一次 O(|t|) 的双指针扫描总时间复杂度是 O(k * |t|_avg)如果k很大效率可能不高。优化思路预处理s。但s通常很短预处理意义不大。更常见的优化是预处理t。我们可以为t构建一个“字符跳转表”。例如对于t “ahbgdc”我们构建一个数组next_pos[i][ch]表示从位置i开始下一个字符ch出现的位置。这样在匹配s时我们可以用 O(|s|) 的时间完成因为每次查找下一个匹配字符是 O(1) 的。构建这个表需要 O(26 * |t|) 的时间假设只有小写字母。这在k很大且每个t自身也很长时能显著提升效率。不过在标准的单次查询机试题中不需要这么复杂。6.2 如果“II”代表其他含义如前所述如果“II”代表寻找最短匹配子串那么算法就需要改变。这通常使用滑动窗口或二分查找来解决。滑动窗口维护一个窗口[left, right]在t上滑动。用一个哈希表或数组need记录s中每个字符需要的数量用另一个window记录当前窗口中各字符的数量。移动right扩大窗口直到覆盖了所有s的字符然后移动left收缩窗口以找到最短的满足条件的子串。这本质上是最小覆盖子串问题的简化版因为这里只要求字符按顺序出现而非连续出现所有字符所以更复杂一些可能需要结合双指针和队列。二分查找如果t非常长且需要多次查询不同的s可以预处理t记录每个字母出现的所有位置索引列表是有序的。对于s中的每个字符我们在这个字符的位置列表中二分查找大于上一个匹配位置的最小索引。如果找不到则失败。这种方法每次查询的时间复杂度是 O(|s| * log|t|)。6.3 机试中的实战技巧先写思路注释在代码编辑器里先花1-2分钟用注释写下算法步骤。这能帮你理清思路避免写到一半逻辑混乱。使用清晰的变量名i_s,i_t比i,j更清晰sIndex,tIndex也不错。写完立刻测试边界在脑子里或草稿上跑一下空串、单字符、s更长等边界情况。利用本地IDE调试如果环境允许将样例输入复制到本地提前写好的代码中运行确保输出格式完全一致比如大小写、是否换行。时间管理这道题属于简单/中等难度目标是在15-20分钟内完成读题、构思、编码、测试。如果卡壳超过10分钟考虑是不是理解错了题意。这道“字符串子序列II”题目就像一把钥匙打开的是解决字符串匹配类问题的大门。掌握其核心的双指针思想并能根据“II”代表的不同约束灵活变通你在华为OD机试乃至后续的技术面试中遇到类似的题目就能从容应对。编程能力的提升没有捷径就是通过这样一道道经典题目的深入思考和反复练习把别人的思路内化成自己的肌肉记忆。
)
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
