LeetCode 1023 驼峰式匹配：从精确匹配到子序列的“双字符串双指针“模板推导

LeetCode 1023 驼峰式匹配从精确匹配到子序列的双字符串双指针模板推导【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇基于题解仓库 problems/1023.camelcase-matching.md 中的原始解法完整还原 LeetCode 1023「驼峰式匹配」的题目定义、三阶段递进推导过程与 Python 参考实现并结合仓库中 91/two-pointers.md 的双指针专题讲透两个指针分别指向两个不同字符串这一变体模板的识别条件、分支逻辑与复杂度细节读完后可独立套用到同类模式串 可插入字符的匹配题目。题目描述如果我们可以将小写字母插入模式串pattern得到待查询项query那么待查询项与给定模式串匹配。我们可以在任何位置插入每个字符也可以插入 0 个字符。给定待查询列表queries和模式串pattern返回由布尔值组成的答案列表answer只有在queries[i]与pattern匹配时answer[i]才为true否则为false。示例 1输入queries [FooBar,FooBarTest,FootBall,FrameBuffer,ForceFeedBack], pattern FB 输出[true,false,true,true,false] 解释 FooBar 可以这样生成F oo B ar。 FootBall 可以这样生成F oot B all。 FrameBuffer 可以这样生成F rame B uffer。示例 2输入queries [FooBar,FooBarTest,FootBall,FrameBuffer,ForceFeedBack], pattern FoBa 输出[true,false,true,false,false] 解释 FooBar 可以这样生成Fo o Ba r。 FootBall 可以这样生成Fo ot Ba ll。示例 3输入queries [FooBar,FooBarTest,FootBall,FrameBuffer,ForceFeedBack], pattern FoBaT 输出[false,true,false,false,false] 解释 FooBarTest 可以这样生成Fo o Ba r T est。注原始题解文档中示例 3 的输入/输出两行书写顺序颠倒此处已按题目语义修正为输入为 queries 与 pattern输出为布尔列表。约束条件1 queries.length 1001 queries[i].length 1001 pattern.length 100所有字符串仅由大写和小写英文字母组成。规则的形式化匹配条件到底意味着什么原始规则只有一句话——把小写字母插入 pattern 得到 query。在写指针之前先把这条规则展开成可直接编码的判定条件query 中的所有大写字母必须全部来自 pattern插入操作只允许插入小写字母因此 query 里任何无法被 pattern 提供的字符如果是个大写字母匹配立即失败。这也是最终算法中遇到不同字母且 query[i] 不是小写则返回 False一行的理论来源。pattern 的每个字符无论大小写都必须按序出现在 query 中插入操作不改变 pattern 原有字符的相对顺序所以 pattern 是 query 的一个子序列pattern 的指针只前进、不跳跃。query 中多余的字符必须全部是小写字母这些多余字符就是被插入进去的部分。把这三条想清楚题目就从字符串变形问题变成了带约束的双指针扫描问题。前置知识双指针的两字符串变体这道题的前置知识是双指针。需要特别说明的是题解原文在思路部分明确指出这道题的双指针并不是指向同一个数组或者字符串而是指向两个分别是 query 和 pattern。这种题目非常常见能够识别和掌握这种题目的解题模板非常重要。在仓库的双指针专题 91/two-pointers.md 中双指针被划分为三类常见题型快慢指针两个指针步长不同、左右端点指针分别指向头尾向中间移动、固定间距指针间距与步长相同。1023 所用的形态属于该专题讨论的更一般情况——两个指针分别独立地在两个不同序列上单调前进其共同特征是每个指针最多只走一遍序列因此单次扫描的时间复杂度为线性空间复杂度为 O(1)。专题中也提到掌握算法框架的好处碰到新问题时按套路穷举匹配这正对应本篇三阶段推导的展开方式。思路三阶段递进推导题解采用的推导路径是精确匹配 → 子序列匹配 → 加入小写插入规则。每个阶段只在上一个阶段的基础上修改一条规则非常适合学习如何从一个熟悉模板生长出新解法。阶段一去掉插入规则的精确匹配假设没有可以在任何位置插入每个字符也可以插入 0 个字符这条规则问题退化为判断两个字符串是否逐位一致建立两个指针i和j分别指向 query 和 pattern 的首字母当i和j指向的字母相同时同时向后移动两个指针一个单位当i和j指向的字母不同时直接返回 False。阶段二放宽为子序列匹配LeetCode 392 判断子序列进一步放宽不要求逐位一致只要求 pattern 按序出现在 query 中。此时指针运动规则变为建立两个指针i和j分别指向 query 和 pattern 的首字母当i和j指向的字母相同时同时向后移动两个指针一个单位当i和j指向的字母不同时只移动 i 指针跳过 query 中多余字符而 pattern 不能跳当i超出 query 范围时只需判断 pattern 是否也达到了终点当然也可以提前退出。这正是 LeetCode 392「判断子序列」的标准解法给定字符串 s 和 t判断 s 是否为 t 的子序列原文给出的参考代码如下class Solution: def isSubsequence(self, s: str, t: str) - bool: i 0 j 0 while j len(t): if i len(s) and s[i] t[j]: i 1 j 1 else: j 1 if i len (s): return True return i len(s)两个细节值得注意其一i len(s)时的提前return True是合法剪枝——s 已完整匹配无论 t 还剩多少都成立其二循环以j len(t)为界循环结束后用i len(s)兜底保证s 恰好耗尽的情形也被正确处理。阶段三加上小写插入规则本题最终形态在阶段二的基础上补回原题规则指针运动规则只改了一条建立两个指针i和j分别指向 query 和 pattern 的首字母当i和j指向的字母相同时同时向后移动两个指针一个单位当i和j指向的字母不同的时候继续判断i指向的字符是否是小写如果是小写只把i向后移动一个单位该字符是被插入的杂质跳过即可如果不是小写即 query 里出现了 pattern 给不了的大写字母直接返回 False。对比三个阶段可以发现从阶段一到阶段三改变的只有失配时允许跳过 query 的哪些字符——精确匹配不允许跳、子序列匹配允许任意跳、本题允许且仅允许跳小写。这就是题解所说的双字符串双指针模板模板骨架不变失配分支的跳过策略才是每道题的定制点。完整代码实现原文给出的 Python 解法对queries中每一项逻辑相同逐项套用上面的模板class Solution: def camelMatch(self, queries: List[str], pattern: str) - List[bool]: res [] for query in queries: i 0 j 0 while i len(query): if j len(pattern) and query[i] pattern[j]: i 1 j 1 elif query[i].islower(): i 1 else: break if i len(query) and j len(pattern): res.append(True) else: res.append(False) return res下面结合阶段三的推导逐行解析各分支的语义匹配分支if j len(pattern) and query[i] pattern[j]先判断j len(pattern)是必要的——当 pattern 已经耗尽时不能再比较否则会越界此时 query 剩下的部分必须全部是小写字母才有救控制流会自然落入elif/else分支。小写跳过分支elif query[i].islower()对应规则 4query 中未被 pattern 消耗的小写字符一律视为插入字符跳过。大写失配分支else: break对应规则 5query 中出现 pattern 无法提供的或顺序对不上的大写字母立即终止本次匹配。注意这里是break而非直接写结果统一交由循环后的终态判断收口。终态判断i len(query) and j len(pattern)只有当两个指针同时到达各自终点才判 true。这一行一次性覆盖了三种失败情形break导致i len(query)query 耗尽但 pattern 还有剩余j len(pattern)pattern 耗尽后 query 又冒出一个大写字母被break。用示例 1 中的两个关键样例走一遍验证分支行为ForceFeedBackvsFBF与F匹配后j指向B随后o, r, c, e依次走小写跳过分支直到i指向第二个F——它是大写且与B不等走else分支break终态i ! len(query)判false。这正对应插入规则只允许插入小写字母第二个 F 无来源。FrameBuffervsFBF匹配rame小写跳过B匹配uffer小写跳过两指针同时到达终点判true。复杂度分析原始题解给出的结论是其中 N 为 queries 的长度M 为 queries 的平均长度P 为 pattern 的长度时间复杂度O(N * M * P)空间复杂度O(1)从源码结构看这个估计成立但偏松内层while循环中i单调递增每个 query 至多走 M 步每步的比较与指针更新都是 O(1)j只增不减不存在回溯因此总时间复杂度实际可收紧到 O(N * M)原文的 O(N * M * P) 因 P 1是一个依然正确但更宽松的上界。空间上除结果列表外只用了两个指针变量额外空间为 O(1)。在本题queries.length 100、单个字符串长度 100的约束下该解法的最坏操作量约为 10^4 次字符比较级别完全够用不需要为小数据规模做额外优化。扩展还有没有更优秀的解法原解法最后留了一个开放问题这是一个符合直觉的解法但是却不是一个很优秀的解法那么你有想到什么优秀的解法么围绕这段代码的结构可以从两个角度思考优化空间以下均为基于代码结构的推断方向而非已验证的实测结论利用 query 集合的公共前缀当前实现中每个 query 都从i j 0独立扫描queries 之间共享的前缀如示例中大量的Foo开头被重复处理。从源码结构看若把 queries 组织成 Trie、在树节点上共享pattern 匹配进度即每个节点只记录走到 pattern 的第几个位置公共前缀的扫描就能被摊薄。利用 pattern 中大写字母的定位信息由于 query 中只有小写字母可以被跳过pattern 里每个大写字母在 query 中的候选位置其实可以先通过大写字母序列做一次对齐。可以推断预处理 pattern 的大写字母序列后单次判断的分支判断会更少但在本题约束长度均不超过 100下收益有限。对本题而言双指针解法代码短、边界少、不易写错是性价比最高的选择优化方向更适合在queries 数量极大且共享前缀多的场景下考虑。关键点与同类问题原解法归纳的关键点为双指针、字符串匹配、子序列、子串。可以把它们理解为一组检索关键词——以后看到字符串 A 能否通过插入/删除若干字符得到字符串 B的题目先判断约束落在子串 / 子序列 / 带大小写约束的子序列哪一种上再套用本文阶段一、二、三中对应的失配分支策略。本专题中可直接迁移的近邻题目包括 LeetCode 392「判断子序列」阶段二原型以及各类编辑受限的字符串匹配题。仓库中与本文相关的延伸阅读路径本题原始题解problems/1023.camelcase-matching.md双指针专题题型分类与伪代码模板91/two-pointers.md题解文档模板本文结构与其保持一致templates/problems/1014.best-sightseeing-pair.md【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考