单词规律深度解析：从双射到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 对应 dog，b 对应 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

为什么需要两个表？我们再回到pattern="abba", s="dog 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 第一次出现记 0，cat 第一次出现记 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(n+m)。放到单词场景里，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; Map<Character, String> p2w = new HashMap<>(); Map<String, 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) { vector<string> words; stringstream ss(s); string word; while (ss >> word) words.push_back(word); if (pattern.size() != words.size()) return false; unordered_map<char, string> p2w; unordered_map<string, 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_map<char, 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)

比如 pattern="abba"编码为[0,1,1,0]，words=["dog","cat","cat","dog"]编码也为[0,1,1,0]。两个列表相等，返回 true。如果某个字符第一次出现时分配的序号和单词第一次出现时分配的序号对不上，编码就不相等，直接判 false。

这种写法实际上是把两个独立问题的结构同时抽象成“首次出现序号序列”，不再需要显式维护双向映射。它和双表方案在逻辑上是等价的，但代码更简洁，也更能体现“模式匹配是对结构做抽象”这个精髓。

4.4 边界条件清单：写代码前先在纸上过一遍

无论用哪种实现，边界条件都是这题的隐形炸弹。我整理了一份清单，你可以直接拿来当自测用例：

特别注意：Java 的split(" ")会丢弃末尾的空字符串，所以如果输入s="dog 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_id=123, user=456, cost=10ms。要做异常检测或结构化日志提取，你就得先识别出哪些位置是模板定死的，哪些位置是变量。

一种经典做法是拿一批日志做“模式归纳”：如果多个日志行在相同位置上有相同内容，说明那是模板；不同内容则是变量。这一步本质上是在做模式与序列的对齐。你在单词规律里学到的“抽象成符号序列再比较”的思路，可以直接映射到批量日志聚类上——先把每条日志的固定部分用占位符替换，再比较两条日志的结构编码是否一致。更底层的序列比对问题，比如 DNA 序列匹配，也是同一个祖宗。

5.4 更大视野：从单词规律看整个模式匹配谱系

把单词规律放回模式匹配的大谱系里，你会发现它处于非常基础但承上启下的位置。再往下，是两个字符串的相等性比较，那是数据结构里的equals问题；往旁，是单模式匹配，KMP、Boyer-Moore 是代表；再往上是多模式匹配，AC 自动机；再往上，是带通配符和重复的正则匹配；如果模式本身也需要学习，那就进入机器学习里的序列标注领域了，比如条件随机场。

这么说有点抽象，但我始终认为，学习算法最重要的是在脑子里建立“谱系”。你刷一道题，如果能说出它在整个知识网络里的位置，以及它和相邻问题的区别，那比单纯背十道题的解法有价值得多。单词规律就是很好的样本：它用最简单的形式，把“匹配”这个动作的核心约束展示给你看，理解了它，你再看 KMP、AC 自动机、正则引擎，会发现它们不过是把同一个思想在不同复杂度下展开了而已。

6. 面试现场实录与高频追问

6.1 面试官最爱问的几个追问

这道题当面试题出现时，真正的考验不只是写出来，而是能不能扛住追问。我把常见的追问和推荐回答整理如下：

• 为什么需要两个哈希表，一个不行吗？推荐回答：因为需要保证双射，正向表只约束了模式字符到单词的映射唯一性，无法约束多个模式字符映射到同一个单词的情况，反向表负责拦截这种冲突。
• 能不能优化空间？推荐回答：如果模式字符限定为 26 个小写字母，可以用数组代替正向 map；反向约束可以改用 set 记录已使用过的单词，这样空间从两个 map 降到一个 set 和一个数组。
• 时间复杂度是多少？推荐回答：拆分 O(n)，遍历 O(m)，整体 O(n+m)，空间 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 自动机、正则引擎和工程模板校验一整条知识链。

我从第一次写单表方案翻车，到后来用双表、用编码串、再到把它讲给团队里做路由配置校验的同事听，整个过程最大的体会是：所谓算法之美，往往不是复杂炫技，而是在最朴素的问题里藏着的普适逻辑。下次你再看这类“简单题”，不妨多问自己一句——它真的只是表面看起来那么简单吗？想清楚这一层，你就已经走在很多人前面了。