前几天在群里看到有人聊 LeetCode 的“单词规律”Word Pattern这道题有同学说“这不就拆开字符串拿哈希表比对一下吗”我盯着那行“简单”看了半天心里想的是这道题要是真这么简单就不会被这么多公司拿来当面试题了。单词规律这个题目表面上是字符串处理实际上是模式匹配里最典型也最容易被低估的一个场景。它要求你判断一个模式串和一个句子里的单词是否“一一对应”这背后涉及的是映射关系、双射约束、序列编码甚至能一路延伸到 KMP、AC 自动机、正则引擎的设计思路。换句话说你刷的不仅是一道哈希表题你在触摸一套模式匹配家族的地基。这篇文章我想从题目本身出发把这道题讲透暴力枚举怎么起步、为什么必须用双向映射、它和 KMP 之间到底有什么关系、工程里哪些场景每天都在用同一套思想最后再给你一份能直接复现的代码和面试应答清单方便你不仅“会做”还能“讲明白”。1. 先把题目说人话它到底在判断什么1.1 一个看起来有手就行的入门题题目本身不复杂。给定一个模式串 pattern比如abba再给一个句子 s比如dog cat cat dog你要判断句子里的单词顺序是不是符合这个模式。符合就返回 true不符合就返回 false。几个标准例子你应该很熟了pattern abba, s dog cat cat dog返回 true因为 a 对应 dogb 对应 cat结构完全一致。pattern abba, s dog cat cat fish返回 false最后一个词没有按 a 的映射来。pattern abba, s dog dog dog dog返回 false因为 a 和 b 分别对应了 dog但 b 和 a 也对应同一个词这违反了“不同字符必须对应不同单词”的约束。很多人第一次做这题的时候就写了第一版先把 s 按空格拆成单词数组然后一个 for 循环把 pattern 里的字符和单词塞进 HashMap。然后被第二个例子也就是abba - dog dog dog dog这个 case 挂掉了。问题出在哪这个场景不能早退你必须把它说清楚这里要求的不是普通的映射而是双射bijection。前向看每个模式字符必须唯一对应一个单词反向看每个单词也必须唯一对应一个模式字符。两层约束缺一不可。1.2 暴力枚举的起点拆分与对齐一开始想到暴力枚举是很自然的。你要比较两个序列第一步肯定是对齐。字符串没法直接对齐那就先把句子按空格拆开变成单词数组。拆完之后最朴素的做法就是枚举每一个模式字符和它对应的单词建立映射关系。这里的“枚举”其实就是一次线性扫描没有剪枝没有回退。因为题目给的是一个已经约定好的规则序列不存在搜索空间所以暴力解法在这个场景下不会超时。这也是很多人的误区——一听到暴力枚举就觉得低级实际上它是很多高级算法的基础。你可以把 KMP 理解成对“暴力枚举匹配失败时如何高效回退”的优化而单词规律这一步连回退都不需要所以它比 KMP 还简单一层。但有一个细节很容易踩坑枚举之前一定要先检查长度。如果 pattern 的长度和单词个数都不一致直接返回 false这一步省掉后面所有事儿。1.3 映射关系里的数学课单射、满射与双射我想把这一小节单独拎出来因为它是整道题真正想问的东西也是面试官真正想听的东西。在集合论里映射分成几种单射injective要求不同的自变量映射到不同的因变量满射surjective要求每个因变量都被至少一个自变量映射到双射bijection则是既满足单射又满足满射两边元素一一对应。单词规律要求的就是双射。为什么我们可以用翻译来类比如果英文单词“bank”既能翻译成“银行”又能翻译成“河岸”读者还能靠上下文猜但如果有两个英文单词“bank”和“banker”都翻译成同一个中文词“银行”那反过来做中译英时你根本不知道到底该还原成哪个英文单词。正向映射不唯一会造成歧义反向映射不唯一会造成无法还原。这道题要求的是“能唯一还原”的严格对应关系所以必须双向检查。也正是这个原因我才说这道题不是简单的查表。查表只做正向匹配而这里做的是双射校验。你理解了这一层后面所有代码怎么写、为什么写两个 map全都顺理成章了。2. 核心实现剖析哈希表背后的取舍2.1 为什么首选哈希表而不是数组、树既然要做映射那用什么数据结构很多人第一反应是 HashMap因为键值对匹配天生适合哈希表。但如果仔细想这里不是没得选。如果题目明确限制 pattern 只包含 26 个小写字母那完全可以用一个长度为 26 的数组来存映射关系用pattern[i] - a做下标时间 O(1)空间更小。这是 LeetCode 原题没有明说但实际隐含的常见约束。不过面试时主动问一句“模式字符范围是什么”是很加分的行为因为这体现了你对数据结构选型的敏感度。用树形结构如 TreeMap 也可以好处是按键有序但在这道题里没有排序需求反而增加了 O(log n) 的查找开销。所以哈希表是综合最优解。还有一个原因哈希表在 average case 下是 O(1) 查找而扁平数组只适用于字符范围已知且很小的场景。通用解法当然选 HashMap。2.2 双表方案的代码思路与反例分析双表方案是整个解题社区里流传最广、最稳妥的做法准备两个 map一个记录pattern字符 - 单词另一个记录单词 - pattern字符遍历时同时检查。我先把完整思路写成伪代码方便你看清每一步在干什么1. 将 s 按空格拆分成单词数组 words 2. 如果 pattern 长度与 words 长度不等返回 false 3. 初始化 p2w 和 w2p 两个空哈希表 4. 遍历 i 从 0 到 len(pattern)-1 a. 令 c pattern[i], word words[i] b. 如果 c 已经在 p2w 中且 p2w[c] ! word返回 false c. 如果 word 已经在 w2p 中且 w2p[word] ! c返回 false d. 将 (c - word) 和 (word - c) 写入两个表 5. 遍历结束返回 true为什么需要两个表我们再回到patternabba, sdog dog dog dog。正向表 p2w 会建立a - dog, b - dog你检查的时候发现 a 和 b 都存在且各自映射没问题于是返回 true。但反向表 w2p 检查时就会发现dog - a已经存在现在又要写入dog - b冲突了。所以反向表是拦下这个反例的关键。2.3 单表方案的翻车现场你以为省了一个表其实错得离谱常见的自作聪明做法是只维护一个 map比如只存字符 - 单词然后判断时发现当前字符已有映射就对比值否则就写入。这个方案能过一部分用例但永远会在abba - dog dog dog dog或abc - dog dog dog这类用例上挂掉。有同学会反驳那我再加一个set存放已经使用过的单词不就行了你会发现这确实能修复“不同模式字符映射到同一个单词”的问题但本质上你还是引入了第二个集合来存储反向约束只不过表现形式从 map 变成了 set。思路没有变只是代码看起来省了一点。我不推荐这种写法原因有两方面。第一它更容易漏约束比如单词与字符对应的唯一性在并发写场景下很难保证。第二面试官追问时你得解释为什么 set 能替代反向 map因为单词是从句子拆分来的天然唯一所以只需要记录“是否被用过”而反向 map 还能承担字符串与字符的等价性判断。两套方案实际能力等价但双表可读性更高、更不容易误导自己。2.4 复杂度分析别只写代码要说清楚成本时间上拆分字符串需要 O(n)n 是句子长度遍历 pattern 需要 O(m)m 是模式长度。因为题目要求长度一致所以整体时间复杂度是 O(n m)。哈希表的查找和插入平均是 O(1)整体依然线性。空间上两个哈希表分别存储了模式字符到单词的映射和单词到模式字符的映射最坏情况存储 O(m) 个键值对。如果你用数组存 26 个字符的映射那空间还能降到 O(1)这也是一个小优化点。我在面试的时候通常还会补一句如果哈希函数设计不好最坏情况下哈希表会退化到 O(m^2)但是工程实现里基本不会发生语言内置的哈希函数已经足够优秀。3. 向模式匹配深处走它与 KMP、自动机的真正关系3.1 编码串视角把单词流变成符号流现在我想换一个角度把这道题从哈希表里解放出来。单词规律真正在做的事情其实是“把两个不同层面的序列抽象成同一种符号序列再比较”。假设 pattern 是abba我们可以按每个字符第一次出现的顺序把它编码成0 1 1 0。句子dog cat cat dog同样处理dog 第一次出现记 0cat 第一次出现记 1于是也得到0 1 1 0。两个编码串相等所以匹配成功。如果句子是dog cat cat fish编码会变成0 1 1 2和0 1 1 0不相等匹配失败。这就是 KMP 里的核心思想雏形把文本和模式都抽象成符号序列然后在符号序列上做等价性判断。KMP 的 next 数组本质上是“在模式串内部寻找最长的相同前缀后缀”它研究的不是文本内容而是模式的结构。单词规律也一样它不关心单词具体是什么只关心结构是否一致。3.2 KMP 为什么适合这类匹配问题失配时的跳跃如果你把问题升级一下变成“给定一个长文本句子流判断其中是否存在某一段单词符合 pattern”那就不能用线性扫描一次搞定了。因为你不知道匹配的起始位置需要在每个位置都尝试匹配最坏情况下会 O(n*m) 甚至更高。这时候 KMP 的价值就出来了。KMP 在匹配失败时不是回到模式串开头重新匹配而是利用 next 数组跳到已经匹配过的公共前后缀位置整体复杂度降到 O(nm)。放到单词场景里next 数组就不再基于字符而是基于“单词的结构编码”——两个单词是否相等可以通过哈希值快速判断。如果你对 KMP 已经忘了我给你一个直觉它就像你在一本书里找一句话失败的时候你不是回到第一个字重新读而是直接翻到上次匹配到一半、但能和这句话开头重合的地方继续读。这个“重合长度”就是 next 数组的意义。3.3 从单词规律到 AC 自动机、正则引擎理解到这一层你可以继续往前推如果一个 pattern 不够要同时匹配多个 pattern怎么办那就是多模式匹配问题AC 自动机登场。AC 自动机可以理解成“KMP Trie 树”它在多模式场景下把每个模式的失配跳转都建好扫描一次文本就能找出所有模式串的匹配位置。如果你再把模式变成带通配符、带重复量词的形式比如a*b那就进入正则表达式引擎的领域了。正则引擎本质上是把模式编译成 NFA 或 DFA然后在文本上模拟状态机。单词规律里的“每个字符映射到一个单词”就是最简化的确定性匹配而正则里的.*这种灵活性相当于打破了双射约束允许一个模式符号匹配任意多内容。所以我经常跟朋友说LeetCode 上很多“简单题”其实都是一棵大树的叶子。单词规律挂在这棵树的哪根枝上模式表示与匹配的枝。顺着它往深了走KMP、Trie、AC 自动机、正则引擎全在这一条路上。3.4 剪枝与搜索当约束变复杂时暴力就不行了热搜词里常有“暴力枚举算法”和“剪枝算法”这两个词和单词规律也有关联。如果题目变成给你一个句子求所有能让句子符合某种模式的 pattern 组合那你面临的就是组合爆炸问题需要对每个字符枚举它可能对应的单词集合。纯暴力枚举的复杂度和字符种类、单词数量成指数关系这时就需要剪枝一旦发现某个字符已经被使用的单词序列和当前单词冲突立刻剪掉整棵子树。再进一步可以用回溯算法在搜索树上走配合哈希表记录当前路径上已经建立的映射避免重复计算。单词规律这道题因为约束强、一对一搜索空间被压缩到只有一条路径所以看起来不需要剪枝。但你要有意识它在更复杂的匹配约束下就是回溯剪枝的原型。有了这层意识以后做正则表达式匹配、通配符匹配、语义分割标签对齐之类的问题时你会更容易联想起来。4. 一份可复现的参考实现4.1 Python 版本与一行流的骚操作最直接的 Python 写法如下核心就是双表同步校验def wordPattern(pattern: str, s: str) - bool: words s.split() if len(pattern) ! len(words): return False p2w {} w2p {} for c, w in zip(pattern, words): if c in p2w: if p2w[c] ! w: return False else: p2w[c] w if w in w2p: if w2p[w] ! c: return False else: w2p[w] c return True如果是在刷题环境里想秀一下Python 还有更简洁的等价写法def wordPattern(pattern: str, s: str) - bool: words s.split() if len(pattern) ! len(words): return False return len(set(pattern)) len(set(words)) len(set(zip(pattern, words)))这个一行流背后的原理很有意思set(pattern)是模式字符的种类数set(words)是单词种类数set(zip(pattern, words))是配对种类数。当这三个数相等时说明每种字符只对应一种单词每种单词也只对应一种字符恰好就是双射条件。我第一次看到这个写法时愣了一下想了十分钟才反应过来它为什么是对的。说实话我不太建议在正式代码里用这种写法因为可读性不如双表但作为脑力体操确实值回票价。4.2 Java 与 C 实现要点Java 版本要注意两个点split 的正则行为和基本类型比较。先看代码public boolean wordPattern(String pattern, String s) { String[] words s.split( ); if (pattern.length() ! words.length) return false; MapCharacter, String p2w new HashMap(); MapString, Character w2p new HashMap(); for (int i 0; i pattern.length(); i) { char c pattern.charAt(i); String w words[i]; if (p2w.containsKey(c) !p2w.get(c).equals(w)) return false; if (w2p.containsKey(w) w2p.get(w) ! c) return false; p2w.put(c, w); w2p.put(w, c); } return true; }这里w2p.get(w) ! c用的是字符比较因为 c 是 char 基本类型而w2p的 get 返回的是 Character 对象。Java 对基本类型和包装类比较时如果是char和Character混在一起会自动拆箱为 char 再比较所以!是安全的。但如果你写成!w2p.get(w).equals(c)也是对的只是没必要。C 版本用 unordered_map代码更像 Java 版本bool wordPattern(string pattern, string s) { vectorstring words; stringstream ss(s); string word; while (ss word) words.push_back(word); if (pattern.size() ! words.size()) return false; unordered_mapchar, string p2w; unordered_mapstring, char w2p; for (int i 0; i pattern.size(); i) { char c pattern[i]; if (p2w.count(c) p2w[c] ! words[i]) return false; if (w2p.count(words[i]) w2p[words[i]] ! c) return false; p2w[c] words[i]; w2p[words[i]] c; } return true; }C 里如果只用一个 map比如unordered_mapchar, string你依然会在abba - dog dog dog dog上翻车原因和前面一样这里不再重复。4.3 一个更精妙的变体首次出现位置编码法如果你能理解 3.1 小节的编码串视角那这个变体就会让你眼前一亮。我们不需要两个 map只用两个 map 分别记录“当前元素第一次出现的下标/序号”然后比较两个编码序列是否完全一致。def wordPattern(pattern: str, s: str) - bool: words s.split() if len(pattern) ! len(words): return False def encode(seq): first_pos {} result [] for x in seq: if x not in first_pos: first_pos[x] len(first_pos) result.append(first_pos[x]) return result return encode(pattern) encode(words)比如 patternabba编码为[0,1,1,0]words[dog,cat,cat,dog]编码也为[0,1,1,0]。两个列表相等返回 true。如果某个字符第一次出现时分配的序号和单词第一次出现时分配的序号对不上编码就不相等直接判 false。这种写法实际上是把两个独立问题的结构同时抽象成“首次出现序号序列”不再需要显式维护双向映射。它和双表方案在逻辑上是等价的但代码更简洁也更能体现“模式匹配是对结构做抽象”这个精髓。4.4 边界条件清单写代码前先在纸上过一遍无论用哪种实现边界条件都是这题的隐形炸弹。我整理了一份清单你可以直接拿来当自测用例场景输入示例预期结果原因长度不一致pattern ab, s dogfalsepattern 长度 2单词数 1正向冲突pattern ab, s dog cat和dog mouse混合场景false同一字符映射到不同单词反向冲突pattern ab, s dog dogfalse不同字符映射到同一单词一个字符一个词pattern a, s dogtrue最简情况空字符串pattern , s true两边都为空空 pattern非空 spattern , s dogfalse长度不一致重复模式pattern aaa, s dog dog dogtrue一个字符对应一个单词没有冲突特别注意Java 的split( )会丢弃末尾的空字符串所以如果输入sdog cat cat dog 分词结果依然只有 4 个单词不会因为你多加了个空格就报错。但如果单词之间连续多个空格split( )会产生空字符串导致匹配错乱这时应该用split(\\s)。Python 的split()默认会把连续空白符都当分隔符反而更省心。5. 这道题在工程里的真身5.1 配置模板与数据校验每个框架都在做的双射检查单词规律在工程里最常见的投影就是配置系统里的模板校验。很多配置框架允许你声明一个模板里面用占位符表示动态值然后用户提交的数据必须匹配这个模板。比如一个日志配置模板是{timestamp} {level} {message}用户提交的配置就必须满足第一段是时间第二段是级别第三段是消息顺序和占位符都不能乱。做这种校验时你要做的事和单词规律几乎一样把模板抽象成模式串把用户数据抽象成单词序列然后检查双射关系。不同点在于工程里的键大多不是单个字符而是{timestamp}这种长字符串而且校验方向可能只要求模板到值的单向映射就够。但只要涉及“占位符可复用、两段内容不能同一个占位符”这类约束双射思想就派上用场。5.2 URL 路由与路径模板匹配Web 框架里的远房亲戚任何一个 Web 框架都有路由模块路由规则写的是/api/{version}/user/{id}请求进来的是/api/v1/user/123。框架要做的事就是把路由模板里的{version}和{id}占位符与实际请求路径中的v1、123做绑定。这不就是单词规律吗模板字符{version}对应实际片段v1{id}对应123。如果同一个请求路径片段可以匹配多个模板占位符路由就会产生歧义如果同一个模板占位符匹配了不同路径片段框架就不知道该把哪个值传给处理函数。生产级框架解决这个问题的方案通常是在模板编译阶段把路径解析成带类型的节点序列再基于 Trie 树做高并发匹配底层依然是对齐和双射。5.3 日志模式提取与序列数据对齐另一个容易忽略的场景是日志解析。线上服务的日志通常由固定模板和动态变量组成比如request_id123, user456, cost10ms。要做异常检测或结构化日志提取你就得先识别出哪些位置是模板定死的哪些位置是变量。一种经典做法是拿一批日志做“模式归纳”如果多个日志行在相同位置上有相同内容说明那是模板不同内容则是变量。这一步本质上是在做模式与序列的对齐。你在单词规律里学到的“抽象成符号序列再比较”的思路可以直接映射到批量日志聚类上——先把每条日志的固定部分用占位符替换再比较两条日志的结构编码是否一致。更底层的序列比对问题比如 DNA 序列匹配也是同一个祖宗。5.4 更大视野从单词规律看整个模式匹配谱系把单词规律放回模式匹配的大谱系里你会发现它处于非常基础但承上启下的位置。再往下是两个字符串的相等性比较那是数据结构里的equals问题往旁是单模式匹配KMP、Boyer-Moore 是代表再往上是多模式匹配AC 自动机再往上是带通配符和重复的正则匹配如果模式本身也需要学习那就进入机器学习里的序列标注领域了比如条件随机场。这么说有点抽象但我始终认为学习算法最重要的是在脑子里建立“谱系”。你刷一道题如果能说出它在整个知识网络里的位置以及它和相邻问题的区别那比单纯背十道题的解法有价值得多。单词规律就是很好的样本它用最简单的形式把“匹配”这个动作的核心约束展示给你看理解了它你再看 KMP、AC 自动机、正则引擎会发现它们不过是把同一个思想在不同复杂度下展开了而已。6. 面试现场实录与高频追问6.1 面试官最爱问的几个追问这道题当面试题出现时真正的考验不只是写出来而是能不能扛住追问。我把常见的追问和推荐回答整理如下为什么需要两个哈希表一个不行吗推荐回答因为需要保证双射正向表只约束了模式字符到单词的映射唯一性无法约束多个模式字符映射到同一个单词的情况反向表负责拦截这种冲突。能不能优化空间推荐回答如果模式字符限定为 26 个小写字母可以用数组代替正向 map反向约束可以改用 set 记录已使用过的单词这样空间从两个 map 降到一个 set 和一个数组。时间复杂度是多少推荐回答拆分 O(n)遍历 O(m)整体 O(nm)空间 O(m)。如果模式字符集固定为 26空间可以视为 O(1)。如果不允许用哈希表还能怎么做推荐回答可以用数组加 set或者用编码串比较法。但核心还是要保证双射不能只做单向匹配。如果单词特别长或者特别多哈希冲突变严重怎么办推荐回答可以换用平衡树 map最坏复杂度从 O(m^2) 降为 O(m log m)实际工程里很少这么极端但可以提一下。这类追问考察的不是背答案而是你有没有想清楚数据结构选型背后的权衡。你不要怕说“我倾向于用哈希表因为它平均情况最优”面试官想听到的就是这种有根据的决策过程。6.2 常见翻车点与排查技巧写这道题最容易翻车的几个地方我在面试别人时见过太多次了第一个忘了长度检查。很多人一上来就遍历然后 index out of bounds。解决方案是第一步就做长度比较。第二个只用一个 map。这在简单用例上没问题但遇到abba - dog dog dog dog就直接炸。排查技巧是构造“反向冲突”用例来自测而不是只拿正向冲突用例测。第三个把containsKey写成get ! null判断。如果哈希表里存的值本身可能为 null这种写法会误判。虽然这道题里 value 不会是 null但不建议养成坏习惯。第四个Java 的 split 正则陷阱。如果输入句子里有连续多个空格split( )会返回空字符串。排查技巧是打印分出来的数组长度和内容不要假设输入格式完美。第五个在循环里同时更新两个 map 时顺序出错。如果你先更新了 p2w再检查 w2p那 w2p 可能已经因为新写入而盖掉了旧值导致冲突检测失效。正确做法是先做两次检查再统一写入。6.3 从这道题延伸出去的一个思考习惯最后聊一个我自己的方法论刷题时养成“变参设问”的习惯。拿到单词规律你可以问自己四个变体问题如果 pattern 里的字符可以重复无限次但单词是有限的怎么改相当于正则里的和*。如果句子不是空格分隔而是逗号分隔代码哪里会受影响相当于分隔符抽象。如果匹配不要求全串只要找到一段符合 pattern 的子串怎么做这就进入 KMP 的领域。如果 pattern 本身很长包含成千上万个字符怎样保证内存不爆可以考虑把 pattern 做哈希编码用编码串比较。每问一个问题你就把一个简单题往深处推了一步。推着推着你会发现算法题之间不再是孤岛而是一张彼此连接的网。单词规律是绝佳的“入口题”它简单到新手能跑通又深到能带出 KMP、AC 自动机、正则引擎和工程模板校验一整条知识链。我从第一次写单表方案翻车到后来用双表、用编码串、再到把它讲给团队里做路由配置校验的同事听整个过程最大的体会是所谓算法之美往往不是复杂炫技而是在最朴素的问题里藏着的普适逻辑。下次你再看这类“简单题”不妨多问自己一句——它真的只是表面看起来那么简单吗想清楚这一层你就已经走在很多人前面了。
单词规律深度解析：从双射到KMP的模式匹配思维
前几天在群里看到有人聊 LeetCode 的“单词规律”Word Pattern这道题有同学说“这不就拆开字符串拿哈希表比对一下吗”我盯着那行“简单”看了半天心里想的是这道题要是真这么简单就不会被这么多公司拿来当面试题了。单词规律这个题目表面上是字符串处理实际上是模式匹配里最典型也最容易被低估的一个场景。它要求你判断一个模式串和一个句子里的单词是否“一一对应”这背后涉及的是映射关系、双射约束、序列编码甚至能一路延伸到 KMP、AC 自动机、正则引擎的设计思路。换句话说你刷的不仅是一道哈希表题你在触摸一套模式匹配家族的地基。这篇文章我想从题目本身出发把这道题讲透暴力枚举怎么起步、为什么必须用双向映射、它和 KMP 之间到底有什么关系、工程里哪些场景每天都在用同一套思想最后再给你一份能直接复现的代码和面试应答清单方便你不仅“会做”还能“讲明白”。1. 先把题目说人话它到底在判断什么1.1 一个看起来有手就行的入门题题目本身不复杂。给定一个模式串 pattern比如abba再给一个句子 s比如dog cat cat dog你要判断句子里的单词顺序是不是符合这个模式。符合就返回 true不符合就返回 false。几个标准例子你应该很熟了pattern abba, s dog cat cat dog返回 true因为 a 对应 dogb 对应 cat结构完全一致。pattern abba, s dog cat cat fish返回 false最后一个词没有按 a 的映射来。pattern abba, s dog dog dog dog返回 false因为 a 和 b 分别对应了 dog但 b 和 a 也对应同一个词这违反了“不同字符必须对应不同单词”的约束。很多人第一次做这题的时候就写了第一版先把 s 按空格拆成单词数组然后一个 for 循环把 pattern 里的字符和单词塞进 HashMap。然后被第二个例子也就是abba - dog dog dog dog这个 case 挂掉了。问题出在哪这个场景不能早退你必须把它说清楚这里要求的不是普通的映射而是双射bijection。前向看每个模式字符必须唯一对应一个单词反向看每个单词也必须唯一对应一个模式字符。两层约束缺一不可。1.2 暴力枚举的起点拆分与对齐一开始想到暴力枚举是很自然的。你要比较两个序列第一步肯定是对齐。字符串没法直接对齐那就先把句子按空格拆开变成单词数组。拆完之后最朴素的做法就是枚举每一个模式字符和它对应的单词建立映射关系。这里的“枚举”其实就是一次线性扫描没有剪枝没有回退。因为题目给的是一个已经约定好的规则序列不存在搜索空间所以暴力解法在这个场景下不会超时。这也是很多人的误区——一听到暴力枚举就觉得低级实际上它是很多高级算法的基础。你可以把 KMP 理解成对“暴力枚举匹配失败时如何高效回退”的优化而单词规律这一步连回退都不需要所以它比 KMP 还简单一层。但有一个细节很容易踩坑枚举之前一定要先检查长度。如果 pattern 的长度和单词个数都不一致直接返回 false这一步省掉后面所有事儿。1.3 映射关系里的数学课单射、满射与双射我想把这一小节单独拎出来因为它是整道题真正想问的东西也是面试官真正想听的东西。在集合论里映射分成几种单射injective要求不同的自变量映射到不同的因变量满射surjective要求每个因变量都被至少一个自变量映射到双射bijection则是既满足单射又满足满射两边元素一一对应。单词规律要求的就是双射。为什么我们可以用翻译来类比如果英文单词“bank”既能翻译成“银行”又能翻译成“河岸”读者还能靠上下文猜但如果有两个英文单词“bank”和“banker”都翻译成同一个中文词“银行”那反过来做中译英时你根本不知道到底该还原成哪个英文单词。正向映射不唯一会造成歧义反向映射不唯一会造成无法还原。这道题要求的是“能唯一还原”的严格对应关系所以必须双向检查。也正是这个原因我才说这道题不是简单的查表。查表只做正向匹配而这里做的是双射校验。你理解了这一层后面所有代码怎么写、为什么写两个 map全都顺理成章了。2. 核心实现剖析哈希表背后的取舍2.1 为什么首选哈希表而不是数组、树既然要做映射那用什么数据结构很多人第一反应是 HashMap因为键值对匹配天生适合哈希表。但如果仔细想这里不是没得选。如果题目明确限制 pattern 只包含 26 个小写字母那完全可以用一个长度为 26 的数组来存映射关系用pattern[i] - a做下标时间 O(1)空间更小。这是 LeetCode 原题没有明说但实际隐含的常见约束。不过面试时主动问一句“模式字符范围是什么”是很加分的行为因为这体现了你对数据结构选型的敏感度。用树形结构如 TreeMap 也可以好处是按键有序但在这道题里没有排序需求反而增加了 O(log n) 的查找开销。所以哈希表是综合最优解。还有一个原因哈希表在 average case 下是 O(1) 查找而扁平数组只适用于字符范围已知且很小的场景。通用解法当然选 HashMap。2.2 双表方案的代码思路与反例分析双表方案是整个解题社区里流传最广、最稳妥的做法准备两个 map一个记录pattern字符 - 单词另一个记录单词 - pattern字符遍历时同时检查。我先把完整思路写成伪代码方便你看清每一步在干什么1. 将 s 按空格拆分成单词数组 words 2. 如果 pattern 长度与 words 长度不等返回 false 3. 初始化 p2w 和 w2p 两个空哈希表 4. 遍历 i 从 0 到 len(pattern)-1 a. 令 c pattern[i], word words[i] b. 如果 c 已经在 p2w 中且 p2w[c] ! word返回 false c. 如果 word 已经在 w2p 中且 w2p[word] ! c返回 false d. 将 (c - word) 和 (word - c) 写入两个表 5. 遍历结束返回 true为什么需要两个表我们再回到patternabba, sdog dog dog dog。正向表 p2w 会建立a - dog, b - dog你检查的时候发现 a 和 b 都存在且各自映射没问题于是返回 true。但反向表 w2p 检查时就会发现dog - a已经存在现在又要写入dog - b冲突了。所以反向表是拦下这个反例的关键。2.3 单表方案的翻车现场你以为省了一个表其实错得离谱常见的自作聪明做法是只维护一个 map比如只存字符 - 单词然后判断时发现当前字符已有映射就对比值否则就写入。这个方案能过一部分用例但永远会在abba - dog dog dog dog或abc - dog dog dog这类用例上挂掉。有同学会反驳那我再加一个set存放已经使用过的单词不就行了你会发现这确实能修复“不同模式字符映射到同一个单词”的问题但本质上你还是引入了第二个集合来存储反向约束只不过表现形式从 map 变成了 set。思路没有变只是代码看起来省了一点。我不推荐这种写法原因有两方面。第一它更容易漏约束比如单词与字符对应的唯一性在并发写场景下很难保证。第二面试官追问时你得解释为什么 set 能替代反向 map因为单词是从句子拆分来的天然唯一所以只需要记录“是否被用过”而反向 map 还能承担字符串与字符的等价性判断。两套方案实际能力等价但双表可读性更高、更不容易误导自己。2.4 复杂度分析别只写代码要说清楚成本时间上拆分字符串需要 O(n)n 是句子长度遍历 pattern 需要 O(m)m 是模式长度。因为题目要求长度一致所以整体时间复杂度是 O(n m)。哈希表的查找和插入平均是 O(1)整体依然线性。空间上两个哈希表分别存储了模式字符到单词的映射和单词到模式字符的映射最坏情况存储 O(m) 个键值对。如果你用数组存 26 个字符的映射那空间还能降到 O(1)这也是一个小优化点。我在面试的时候通常还会补一句如果哈希函数设计不好最坏情况下哈希表会退化到 O(m^2)但是工程实现里基本不会发生语言内置的哈希函数已经足够优秀。3. 向模式匹配深处走它与 KMP、自动机的真正关系3.1 编码串视角把单词流变成符号流现在我想换一个角度把这道题从哈希表里解放出来。单词规律真正在做的事情其实是“把两个不同层面的序列抽象成同一种符号序列再比较”。假设 pattern 是abba我们可以按每个字符第一次出现的顺序把它编码成0 1 1 0。句子dog cat cat dog同样处理dog 第一次出现记 0cat 第一次出现记 1于是也得到0 1 1 0。两个编码串相等所以匹配成功。如果句子是dog cat cat fish编码会变成0 1 1 2和0 1 1 0不相等匹配失败。这就是 KMP 里的核心思想雏形把文本和模式都抽象成符号序列然后在符号序列上做等价性判断。KMP 的 next 数组本质上是“在模式串内部寻找最长的相同前缀后缀”它研究的不是文本内容而是模式的结构。单词规律也一样它不关心单词具体是什么只关心结构是否一致。3.2 KMP 为什么适合这类匹配问题失配时的跳跃如果你把问题升级一下变成“给定一个长文本句子流判断其中是否存在某一段单词符合 pattern”那就不能用线性扫描一次搞定了。因为你不知道匹配的起始位置需要在每个位置都尝试匹配最坏情况下会 O(n*m) 甚至更高。这时候 KMP 的价值就出来了。KMP 在匹配失败时不是回到模式串开头重新匹配而是利用 next 数组跳到已经匹配过的公共前后缀位置整体复杂度降到 O(nm)。放到单词场景里next 数组就不再基于字符而是基于“单词的结构编码”——两个单词是否相等可以通过哈希值快速判断。如果你对 KMP 已经忘了我给你一个直觉它就像你在一本书里找一句话失败的时候你不是回到第一个字重新读而是直接翻到上次匹配到一半、但能和这句话开头重合的地方继续读。这个“重合长度”就是 next 数组的意义。3.3 从单词规律到 AC 自动机、正则引擎理解到这一层你可以继续往前推如果一个 pattern 不够要同时匹配多个 pattern怎么办那就是多模式匹配问题AC 自动机登场。AC 自动机可以理解成“KMP Trie 树”它在多模式场景下把每个模式的失配跳转都建好扫描一次文本就能找出所有模式串的匹配位置。如果你再把模式变成带通配符、带重复量词的形式比如a*b那就进入正则表达式引擎的领域了。正则引擎本质上是把模式编译成 NFA 或 DFA然后在文本上模拟状态机。单词规律里的“每个字符映射到一个单词”就是最简化的确定性匹配而正则里的.*这种灵活性相当于打破了双射约束允许一个模式符号匹配任意多内容。所以我经常跟朋友说LeetCode 上很多“简单题”其实都是一棵大树的叶子。单词规律挂在这棵树的哪根枝上模式表示与匹配的枝。顺着它往深了走KMP、Trie、AC 自动机、正则引擎全在这一条路上。3.4 剪枝与搜索当约束变复杂时暴力就不行了热搜词里常有“暴力枚举算法”和“剪枝算法”这两个词和单词规律也有关联。如果题目变成给你一个句子求所有能让句子符合某种模式的 pattern 组合那你面临的就是组合爆炸问题需要对每个字符枚举它可能对应的单词集合。纯暴力枚举的复杂度和字符种类、单词数量成指数关系这时就需要剪枝一旦发现某个字符已经被使用的单词序列和当前单词冲突立刻剪掉整棵子树。再进一步可以用回溯算法在搜索树上走配合哈希表记录当前路径上已经建立的映射避免重复计算。单词规律这道题因为约束强、一对一搜索空间被压缩到只有一条路径所以看起来不需要剪枝。但你要有意识它在更复杂的匹配约束下就是回溯剪枝的原型。有了这层意识以后做正则表达式匹配、通配符匹配、语义分割标签对齐之类的问题时你会更容易联想起来。4. 一份可复现的参考实现4.1 Python 版本与一行流的骚操作最直接的 Python 写法如下核心就是双表同步校验def wordPattern(pattern: str, s: str) - bool: words s.split() if len(pattern) ! len(words): return False p2w {} w2p {} for c, w in zip(pattern, words): if c in p2w: if p2w[c] ! w: return False else: p2w[c] w if w in w2p: if w2p[w] ! c: return False else: w2p[w] c return True如果是在刷题环境里想秀一下Python 还有更简洁的等价写法def wordPattern(pattern: str, s: str) - bool: words s.split() if len(pattern) ! len(words): return False return len(set(pattern)) len(set(words)) len(set(zip(pattern, words)))这个一行流背后的原理很有意思set(pattern)是模式字符的种类数set(words)是单词种类数set(zip(pattern, words))是配对种类数。当这三个数相等时说明每种字符只对应一种单词每种单词也只对应一种字符恰好就是双射条件。我第一次看到这个写法时愣了一下想了十分钟才反应过来它为什么是对的。说实话我不太建议在正式代码里用这种写法因为可读性不如双表但作为脑力体操确实值回票价。4.2 Java 与 C 实现要点Java 版本要注意两个点split 的正则行为和基本类型比较。先看代码public boolean wordPattern(String pattern, String s) { String[] words s.split( ); if (pattern.length() ! words.length) return false; MapCharacter, String p2w new HashMap(); MapString, Character w2p new HashMap(); for (int i 0; i pattern.length(); i) { char c pattern.charAt(i); String w words[i]; if (p2w.containsKey(c) !p2w.get(c).equals(w)) return false; if (w2p.containsKey(w) w2p.get(w) ! c) return false; p2w.put(c, w); w2p.put(w, c); } return true; }这里w2p.get(w) ! c用的是字符比较因为 c 是 char 基本类型而w2p的 get 返回的是 Character 对象。Java 对基本类型和包装类比较时如果是char和Character混在一起会自动拆箱为 char 再比较所以!是安全的。但如果你写成!w2p.get(w).equals(c)也是对的只是没必要。C 版本用 unordered_map代码更像 Java 版本bool wordPattern(string pattern, string s) { vectorstring words; stringstream ss(s); string word; while (ss word) words.push_back(word); if (pattern.size() ! words.size()) return false; unordered_mapchar, string p2w; unordered_mapstring, char w2p; for (int i 0; i pattern.size(); i) { char c pattern[i]; if (p2w.count(c) p2w[c] ! words[i]) return false; if (w2p.count(words[i]) w2p[words[i]] ! c) return false; p2w[c] words[i]; w2p[words[i]] c; } return true; }C 里如果只用一个 map比如unordered_mapchar, string你依然会在abba - dog dog dog dog上翻车原因和前面一样这里不再重复。4.3 一个更精妙的变体首次出现位置编码法如果你能理解 3.1 小节的编码串视角那这个变体就会让你眼前一亮。我们不需要两个 map只用两个 map 分别记录“当前元素第一次出现的下标/序号”然后比较两个编码序列是否完全一致。def wordPattern(pattern: str, s: str) - bool: words s.split() if len(pattern) ! len(words): return False def encode(seq): first_pos {} result [] for x in seq: if x not in first_pos: first_pos[x] len(first_pos) result.append(first_pos[x]) return result return encode(pattern) encode(words)比如 patternabba编码为[0,1,1,0]words[dog,cat,cat,dog]编码也为[0,1,1,0]。两个列表相等返回 true。如果某个字符第一次出现时分配的序号和单词第一次出现时分配的序号对不上编码就不相等直接判 false。这种写法实际上是把两个独立问题的结构同时抽象成“首次出现序号序列”不再需要显式维护双向映射。它和双表方案在逻辑上是等价的但代码更简洁也更能体现“模式匹配是对结构做抽象”这个精髓。4.4 边界条件清单写代码前先在纸上过一遍无论用哪种实现边界条件都是这题的隐形炸弹。我整理了一份清单你可以直接拿来当自测用例场景输入示例预期结果原因长度不一致pattern ab, s dogfalsepattern 长度 2单词数 1正向冲突pattern ab, s dog cat和dog mouse混合场景false同一字符映射到不同单词反向冲突pattern ab, s dog dogfalse不同字符映射到同一单词一个字符一个词pattern a, s dogtrue最简情况空字符串pattern , s true两边都为空空 pattern非空 spattern , s dogfalse长度不一致重复模式pattern aaa, s dog dog dogtrue一个字符对应一个单词没有冲突特别注意Java 的split( )会丢弃末尾的空字符串所以如果输入sdog cat cat dog 分词结果依然只有 4 个单词不会因为你多加了个空格就报错。但如果单词之间连续多个空格split( )会产生空字符串导致匹配错乱这时应该用split(\\s)。Python 的split()默认会把连续空白符都当分隔符反而更省心。5. 这道题在工程里的真身5.1 配置模板与数据校验每个框架都在做的双射检查单词规律在工程里最常见的投影就是配置系统里的模板校验。很多配置框架允许你声明一个模板里面用占位符表示动态值然后用户提交的数据必须匹配这个模板。比如一个日志配置模板是{timestamp} {level} {message}用户提交的配置就必须满足第一段是时间第二段是级别第三段是消息顺序和占位符都不能乱。做这种校验时你要做的事和单词规律几乎一样把模板抽象成模式串把用户数据抽象成单词序列然后检查双射关系。不同点在于工程里的键大多不是单个字符而是{timestamp}这种长字符串而且校验方向可能只要求模板到值的单向映射就够。但只要涉及“占位符可复用、两段内容不能同一个占位符”这类约束双射思想就派上用场。5.2 URL 路由与路径模板匹配Web 框架里的远房亲戚任何一个 Web 框架都有路由模块路由规则写的是/api/{version}/user/{id}请求进来的是/api/v1/user/123。框架要做的事就是把路由模板里的{version}和{id}占位符与实际请求路径中的v1、123做绑定。这不就是单词规律吗模板字符{version}对应实际片段v1{id}对应123。如果同一个请求路径片段可以匹配多个模板占位符路由就会产生歧义如果同一个模板占位符匹配了不同路径片段框架就不知道该把哪个值传给处理函数。生产级框架解决这个问题的方案通常是在模板编译阶段把路径解析成带类型的节点序列再基于 Trie 树做高并发匹配底层依然是对齐和双射。5.3 日志模式提取与序列数据对齐另一个容易忽略的场景是日志解析。线上服务的日志通常由固定模板和动态变量组成比如request_id123, user456, cost10ms。要做异常检测或结构化日志提取你就得先识别出哪些位置是模板定死的哪些位置是变量。一种经典做法是拿一批日志做“模式归纳”如果多个日志行在相同位置上有相同内容说明那是模板不同内容则是变量。这一步本质上是在做模式与序列的对齐。你在单词规律里学到的“抽象成符号序列再比较”的思路可以直接映射到批量日志聚类上——先把每条日志的固定部分用占位符替换再比较两条日志的结构编码是否一致。更底层的序列比对问题比如 DNA 序列匹配也是同一个祖宗。5.4 更大视野从单词规律看整个模式匹配谱系把单词规律放回模式匹配的大谱系里你会发现它处于非常基础但承上启下的位置。再往下是两个字符串的相等性比较那是数据结构里的equals问题往旁是单模式匹配KMP、Boyer-Moore 是代表再往上是多模式匹配AC 自动机再往上是带通配符和重复的正则匹配如果模式本身也需要学习那就进入机器学习里的序列标注领域了比如条件随机场。这么说有点抽象但我始终认为学习算法最重要的是在脑子里建立“谱系”。你刷一道题如果能说出它在整个知识网络里的位置以及它和相邻问题的区别那比单纯背十道题的解法有价值得多。单词规律就是很好的样本它用最简单的形式把“匹配”这个动作的核心约束展示给你看理解了它你再看 KMP、AC 自动机、正则引擎会发现它们不过是把同一个思想在不同复杂度下展开了而已。6. 面试现场实录与高频追问6.1 面试官最爱问的几个追问这道题当面试题出现时真正的考验不只是写出来而是能不能扛住追问。我把常见的追问和推荐回答整理如下为什么需要两个哈希表一个不行吗推荐回答因为需要保证双射正向表只约束了模式字符到单词的映射唯一性无法约束多个模式字符映射到同一个单词的情况反向表负责拦截这种冲突。能不能优化空间推荐回答如果模式字符限定为 26 个小写字母可以用数组代替正向 map反向约束可以改用 set 记录已使用过的单词这样空间从两个 map 降到一个 set 和一个数组。时间复杂度是多少推荐回答拆分 O(n)遍历 O(m)整体 O(nm)空间 O(m)。如果模式字符集固定为 26空间可以视为 O(1)。如果不允许用哈希表还能怎么做推荐回答可以用数组加 set或者用编码串比较法。但核心还是要保证双射不能只做单向匹配。如果单词特别长或者特别多哈希冲突变严重怎么办推荐回答可以换用平衡树 map最坏复杂度从 O(m^2) 降为 O(m log m)实际工程里很少这么极端但可以提一下。这类追问考察的不是背答案而是你有没有想清楚数据结构选型背后的权衡。你不要怕说“我倾向于用哈希表因为它平均情况最优”面试官想听到的就是这种有根据的决策过程。6.2 常见翻车点与排查技巧写这道题最容易翻车的几个地方我在面试别人时见过太多次了第一个忘了长度检查。很多人一上来就遍历然后 index out of bounds。解决方案是第一步就做长度比较。第二个只用一个 map。这在简单用例上没问题但遇到abba - dog dog dog dog就直接炸。排查技巧是构造“反向冲突”用例来自测而不是只拿正向冲突用例测。第三个把containsKey写成get ! null判断。如果哈希表里存的值本身可能为 null这种写法会误判。虽然这道题里 value 不会是 null但不建议养成坏习惯。第四个Java 的 split 正则陷阱。如果输入句子里有连续多个空格split( )会返回空字符串。排查技巧是打印分出来的数组长度和内容不要假设输入格式完美。第五个在循环里同时更新两个 map 时顺序出错。如果你先更新了 p2w再检查 w2p那 w2p 可能已经因为新写入而盖掉了旧值导致冲突检测失效。正确做法是先做两次检查再统一写入。6.3 从这道题延伸出去的一个思考习惯最后聊一个我自己的方法论刷题时养成“变参设问”的习惯。拿到单词规律你可以问自己四个变体问题如果 pattern 里的字符可以重复无限次但单词是有限的怎么改相当于正则里的和*。如果句子不是空格分隔而是逗号分隔代码哪里会受影响相当于分隔符抽象。如果匹配不要求全串只要找到一段符合 pattern 的子串怎么做这就进入 KMP 的领域。如果 pattern 本身很长包含成千上万个字符怎样保证内存不爆可以考虑把 pattern 做哈希编码用编码串比较。每问一个问题你就把一个简单题往深处推了一步。推着推着你会发现算法题之间不再是孤岛而是一张彼此连接的网。单词规律是绝佳的“入口题”它简单到新手能跑通又深到能带出 KMP、AC 自动机、正则引擎和工程模板校验一整条知识链。我从第一次写单表方案翻车到后来用双表、用编码串、再到把它讲给团队里做路由配置校验的同事听整个过程最大的体会是所谓算法之美往往不是复杂炫技而是在最朴素的问题里藏着的普适逻辑。下次你再看这类“简单题”不妨多问自己一句——它真的只是表面看起来那么简单吗想清楚这一层你就已经走在很多人前面了。