刷LeetCode的时候第一次碰到“单词规律”Word Pattern这道题我下意识觉得“这不就是做个映射吗”结果真写起来才发现里面全是细节。pattern abbas dog cat cat dog输出true换成dog cat cat fish马上就是false再换成dog dog dog dog还是false。这三个Case跑下来一个比一个刁钻一个比一个能暴露问题。这道题本质上是一个模式匹配问题但它的“模式”是抽象字符而不是具体字符串。它考的不只是哈希表怎么用而是你在处理映射关系时有没有建立“双射”的直觉。这几年我在面试里也经常拿它当热身题发现能一次写对的人不到一半大多数人都栽在只维护了单向映射上。所以这篇博文我想完整拆一下这道题从题目本身开始讲清双射的核心难点再给出可直接照着抄的C实现最后把它放进模式匹配的知识网络里聊聊KMP、同构字符串、回溯剪枝这些关联内容。无论你是在准备算法面试、刷LeetCode还是单纯对模式匹配的底层逻辑感兴趣这篇都能给你一些不一样的视角。1. 题目本身与核心考点拆解1.1 题目到底在说什么题目原文很短给定一个模式串pattern比如abba再给一个字符串s比如dog cat cat dog要求判断s是否满足pattern所表达的规律。所谓满足指的是pattern里的每个字母都唯一映射到s里的一个单词同时s里的每个单词也唯一映射回pattern里的一个字母而且位置顺序完全一致。这个“同时”两个字就是全题的核心。我见过很多人对题目的第一反应是把pattern的字符当key把s的单词当value遍历一遍塞进哈希表就完事。这个思路没有错但它只实现了一半。举个最容易翻车的例子pattern abbas dog dog dog dog。按单向映射a对应dogb也对应dog结束。程序遍历完没发现任何冲突返回true。但正确答案是false因为a和b是两个不同字母它们对应的单词不能相同。这就是所谓“双向唯一对应”的数学结构——双射bijection。读题最关键的收获是这题不是考你会不会用哈希表而是考验你有没有识别出“字符到单词的映射必须是双射”这个条件。1.2 为什么“单向映射”看似合理其实是陷阱很多刷题资料会把这道题归类为“哈希表”简单题导致大家把注意力全放在“怎么建map”上忽略了数学本质。单向映射对应的数学概念是“函数”即每个输入有唯一输出但允许多个输入对应同一个输出。而双射要求的是“一一对应”既不允许一个key对应多个value也不允许多个key对应同一个value。那道题的s dog dog dog dog如果你只查“pattern字符是否出现过”会发现a、b都没出现过于是一路畅通地建立映射最终返回true。但如果你反过来再查一遍“这个单词是否已经被别的字符占用”就会发现dog已经被a占用b再来时就会冲突这才符合真实答案。所以我在给新手讲这道题的时候一定会先用一个生活场景去类比学号和姓名之间的关系。一个学号对应一个学生姓名这是确定的功能但如果两个学号同时指向“张三”你还能分出谁是张三吗单词规律要求的就是“学号-姓名”严格一一对应任何重复都是非法。1.3 解题思路演变从暴力枚举到双哈希如果完全没有数据结构基础遇到这道题会怎么做最原始的做法是暴力枚举先把s按空格拆成单词数组然后针对pattern里的每个位置检查当前字母之前有没有出现过出现过就比对当前单词和之前记录是否相等没出现过就把当前单词加入记录并继续。这个流程本质上就是模拟手工判断时间复杂度O(n^2)也不奇怪。再往上走一步就是哈希表优化。用哈希表把“当前字母出现过”和“对应的单词是什么”缓存下来这样每次查找都是O(1)整道题变成一趟遍历。这里有一个从暴力到优化的关键思维暴力算法在“当前字母出现过”时仍然需要扫描之前的映射记录而哈希表直接把历史记录组织成了可直接寻址的结构。但光有哈希还不够因为前面那个“dog dog dog dog”的反例告诉我们值冲突也需要检查。于是自然的演化就是双哈希一张表存字符到单词的映射另一张表存单词到字符的映射或者一张映射表加一个集合记录已占用单词。这就是双射在工程上的落地。从暴力枚举到双哈希这也是网络上关于“单词规律”最常见的讨论路径。2. 核心难点解析双射与冲突检测2.1 学习映射关系时的方向性陷阱先看一张典型的错误过程表我模拟了很多人写代码时的心理活动步骤读取内容单向映射视角双射视角pattern[0]a, 单词doga → dog未出现记录a → dogdog → a双向记录pattern[1]b, 单词dogb → dogb没出现过记录b → dog但dog已被a占用冲突最终判断truefalse这张表清晰说明只要少了反向检查错误结果就是必然的。代码里体现出来就是“用mapchar, string保存单向映射同时用set 保存已经映射过的单词”。很多人会问那为什么不能用mapstring, char只存方向因为只存反向一样会漏掉“一个字符映射到两个不同单词”的情况比如pattern abbas dog cat cat fish。a第一次记录dog第二次遇到位置3的fish再看mapchar,stringa已经有了dog发现值不一致才返回false。所以正向检查负责“字符不能一对多”反向检查负责“单词不能多对一”缺一不可。2.2 双射的数学直觉从身份证号到学号为了让“双射”不再抽象我最常用的一组类比是身份证号与人名。身份证号和姓名不是双射因为同名的人太多了你拿到一个姓名没法唯一定位到具体的人。而学号和学生姓名在正常教学管理里就应该是双射一个学号只能对应一个学生一个学生也只能拥有一个学号。放在题目场景里pattern里的字母就像学号s里的单词就像学生姓名。系统正常运转的前提就是两者一一对应。如果出现两个学号对应同一个姓名或者一个学号对应两个姓名系统就会乱套。单词规律算法要做的就是给出一个自动化检测“学籍档案是否规范”的方案。这个类比的好处是当你纠结“到底要不要存反向映射”时只要想想“我能不能把一个姓名唯一反查到学号”就知道了。如果你不支持反向查那前面说的“dog被两个字符共占”的情况就根本发现不了。2.3 一个哈希表还是两个代码设计的取舍我见过不少解法只用一个unordered_mapchar, string再配一个unordered_set 来做值占用检查。也有解法直接用两个unordered_map一个存char到string另一个存string到char。两种都能AC但在可读性和健壮性上有区别。用map set的写法主循环只需要一次find操作加一次set的insert操作代码量最少。缺点是当你需要“根据单词反查字符”做某些扩展时set帮不上忙信息不完整。用双map的写法虽然每次要维护两个数据结构但逻辑对称读起来一目了然而且后续如果要支持“给定单词输出对应字符”之类的查询完全不需要重构。我个人在实际刷题和面试手写环节更推荐双map。原因很简单面试脚本不只看你对不对还看沟通成本。你写一个char→string的map面试官第一反应就是“单向映射能过吗”你需要额外解释“我还用set做了反向占用检查”解释成本其实更高。而你直接写双向哈希面试官一眼就能看出你理解了双射。这个选择很微妙但它直接影响你在面试中的表达效率。3. C 实现细节与工程化写法3.1 字符串分割istringstream 是最省心的选择这道题第一步就是把s按空格拆成单词而C标准库不像Python有现成的split于是很多人会自己写循环遍历空格切割。自己切不是不行但连续空格、首尾空格、换行符这些边界情况都要处理非常容易出bug。现实中我推荐直接用istringstream。它天然支持空白字符分割遇到连续多个空格也能自动跳过省去大量边界判断。比如dog cat cat dog这种带多个空格的串istringstream会稳定地依次读出dog、cat、cat、dog行为符合题意。有一点得提醒istringstream处理的是空白字符包括空格、制表符、换行符。如果你只需要按空格切这个行为一般没问题但如果题目明确说“只按空格分开”而输入里混入制表符istringstream会把它们也当成分隔符这可能需要额外注意。好在LeetCode这类平台上的测试输入通常都规规矩矩。3.2 一份可以直接照着写的C代码下面是双map版本的完整实现我在关键位置加了注释class Solution { public: bool wordPattern(string pattern, string s) { // 先把 s 按空白分割成单词 vectorstring words; istringstream iss(s); string word; while (iss word) { words.push_back(word); } // 长度不一致直接 false这是一个快速剪枝 if (pattern.size() ! words.size()) { return false; } // 双向哈希表 unordered_mapchar, string p2s; unordered_mapstring, char s2p; for (int i 0; i pattern.size(); i) { char c pattern[i]; const string w words[i]; // 正向检查字符是否已经映射到别的单词 if (p2s.count(c) p2s[c] ! w) { return false; } // 反向检查单词是否已经被别的字符占用 if (s2p.count(w) s2p[w] ! c) { return false; } // 建立双向映射 p2s[c] w; s2p[w] c; } return true; } };这份代码的核心逻辑就四点分割、长度剪枝、正向查冲突、反向查冲突。所有判断都在一趟循环里完成时间复杂度O(n)空间复杂度O(m)其中n是单词数量m是不同单词数量。我还见过一种更省空间的写法把map换成数组加set。因为pattern里只有小写字母可以用int p2s[26]存字符上次映射的单词编号用unordered_set 记录已占用的单词编号。这样能省掉字符串哈希的开销但对一般面试场景来说收益不大反而增加理解成本。3.3 边界条件与输入健壮性边界条件是最容易被忽视的部分也是测试用例最容易踩到的坑。我总结了一下需要重点验证的场景pattern为空、s为空长度检查会先兜住通常返回true因为空模式匹配空串。pattern为空、s非空长度不匹配返回false。pattern as dog单字符单单词应当返回true。pattern as dog cat长度不匹配直接false。s包含多个连续空格istringstream自动处理分割结果没有空字符串。单词数量特别大时unordered_map查找均摊O(1)并发冲突概率低性能稳定。有一点我吃过亏如果题目在s里混入了非ASCII字符或者全角空格istringstream的默认行为可能跟你预期不一致。更稳妥的做法是在读入前对s做trim去掉首尾空白但内嵌连续空格交给istringstream即可。4. 从单词规律看模式匹配家族的延续4.1 KMP 算法与单词规律的对话很多人看到“模式匹配”这个关键词第一反应是KMP算法。KMP解决的是给定一个文本串T和一个模式串P找出P在T中出现的位置。它处理的是“字面对齐”P abc那么T中必须连续出现abc才算匹配。而单词规律处理的是“结构同构”pattern abba它对应的不一定是具体的dog cat cat dog你也可以用cat dog dog cat来满足它重点在结构而不是字面内容。这两种匹配视角本质上是不同层级的问题。KMP关心“字节是否完全一致”单词规律关心“类别之间的对应关系是否一致”。我在实际工作中很少把这两者混为一谈但刷题时把它们放在一起对比对理解很有帮助。KMP的next数组本质上是在优化暴力枚举的无效回溯而单词规律的双哈希是在优化“历史映射关系的查询”。一个面向“串的重复结构”一个面向“映射关系的合法性”它们共同构成了模式匹配的两种基本坐标系。4.2 同构字符串与单词规律的家族关系LeetCode上有一道几乎“换汤不换药”的题205. 同构字符串Isomorphic Strings。它判断两个字符串s和t是否同构比如s eggt add返回true。这道题跟单词规律的区别仅仅在于把“单词”换成了“字符”核心还是双射代码几乎可以平移用两个map或者一个map加set做双向检查。我把这类题归为“双射家族”题目输入形式数据结构核心考点290. 单词规律pattern字符串 单词串char→string string→char字符串分割 双向映射205. 同构字符串两个字符串char→char char→char双向映射291. 单词规律IIpattern字符串 单词串单词长度不固定哈希 回溯递归回溯 剪枝 映射其中291题是进阶版pattern的每个字符可以匹配一段长度不定的连续子串此时双射仍然成立但你不能遍历一遍就出结果而是要枚举所有可能的切分方式用回溯递归去尝试。它的剪枝操作就是“检查当前映射是否已经冲突”如果没有冲突就继续深搜。这时你会发现单词规律II已经把“双射检查”和“递归枚举”结合在了一起复杂度一下子从线性变成指数级但也正因为有双射约束剪枝效率才足够高。4.3 一个简单的模式匹配题如何考出深度面试官特别喜欢从这种简单题往外扩。我复盘过一轮真实面试面试官就从单词规律开始一路追问出三个问题第一问如果pattern里不只小写字母还有数字和特殊字符怎么办答案是直接换用unordered_map不要用数组。这个考察点其实是数据结构的泛化能力。第二问如果单词长度不固定你怎么解这就是291题的场景。很多候选人能写出回溯框架但忘了回溯时要撤销双向映射导致状态污染。这恰恰是双射思想在递归场景里的应用。第三问如果要求返回所有满足pattern的单词划分而不是只判断存在性怎么做这就要把回溯改成收集所有合法路径剪枝条件同样是双向映射。能走到这一步的候选人通常已经能够灵活地把“双射”从判断工具变成搜索约束。从一道简单题延伸到一整棵知识树这是我觉得模式匹配系列最好玩的地方。它不像动态规划那样需要很强的递推直觉但同样能把“数据结构选型”“边界处理”“递归剪枝”这些基本功串起来。5. 常见问题、性能数据与调试经验5.1 典型错误一只用一个哈希表导致误判这是我在面试中见过最多的问题没有之一。错误代码通常长这样unordered_mapchar, string mp; for (int i 0; i pattern.size(); i) { if (mp.count(pattern[i]) mp[pattern[i]] ! words[i]) { return false; } mp[pattern[i]] words[i]; } return true;这段代码在pattern abbas dog dog dog dog时会返回true而预期结果是false。原因就是它完全没有检查“单词是否已经映射给别的字符”。我把这个Case单独写到测试用例里作为代码提交前的自检标准。建议每个写这道题的人都把“abba / dog dog dog dog”和“abba / dog cat cat fish”这两个反向Case永远留在测试列表里它们一个抓反向冲突一个抓正向冲突。5.2 典型错误二分割字符串时出现空串如果你不用istringstream而自己写split常见的坑是当s以空格开头或者有两个连续空格时会解析出空字符串。空字符串一旦进入words数组长度检查可能仍然通过但映射关系会错乱。比如pattern abs dog cat开头有个空格自己写的分割逻辑可能得到[, dog, cat]长度变成3直接判false但题目预期是true。这个问题在C里最容易用istringstream规避。如果你必须手写分割记得在循环里跳过连续空白int i 0; while (i s.size()) { while (i s.size() isspace(s[i])) i; int start i; while (i s.size() !isspace(s[i])) i; if (start i) words.push_back(s.substr(start, i - start)); }这段代码能正确识别空串边界但明显更啰嗦。工程上能用标准库解决的就别自己造轮子这是我反复强调的一个原则。5.3 性能数据与调试技巧单词规律这道题在LeetCode上我实测最差情况耗时大概在0ms到8ms之间内存消耗约6.5MB到8.5MB取决于map的数量。用双map实现面对上千个单词的输入规模完全没有压力毕竟就是一次线性扫描加若干次哈希读写。调试这道题有个很实用的技巧写一个打印映射关系的辅助函数在每次更新映射后把当前状态打印出来。比如输入是dog cat cat dog你会看到每一步的map内容变化一旦出现双向冲突一眼就能定位是哪个方向的检查漏了。我日常刷题时还会多写几组自定义用例覆盖单字符、单词数量不匹配、模式长度超长、同一单词出现在不同pattern字符下、以及同一pattern字符对应不同单词等场景。把这些用例固化成一份测试清单每次提交前跑一遍比任何复盘都管用。最后再说一个扩展心得如果你觉得双map写法在工程里太重可以用“map set”的组合但一定要把set的作用写在注释里。我踩过几次坑之后发现代码写出来给别人看最重要的不是省那两个变量而是把双射这个约束表达得足够明显。LeetCode上优秀答案那么多区别往往不在算法复杂度而在谁能在30秒内让读代码的人理解你的全部设计意图。这道题恰恰是练习这种表达能力的绝佳素材。