单词规律如何用双向映射判断模式与单词是否一一对应？（LeetCode 290）

简化版

单词规律要求 pattern 中的字符和句子中的单词形成一一对应。既不能一个字符映射到多个单词，也不能多个字符映射到同一个单词。用两个哈希表分别维护 char -> word 和 word -> char，逐位检查即可。

详细版

boolean wordPattern(String pattern, String s) {
    String[] words = s.split(" ");
    if (pattern.length() != words.length) return false;
    Map<Character, String> c2w = new HashMap<>();
    Map<String, Character> w2c = new HashMap<>();
    for (int i = 0; i < pattern.length(); i++) {
        char c = pattern.charAt(i);
        String w = words[i];
        if (c2w.containsKey(c) && !c2w.get(c).equals(w)) return false;
        if (w2c.containsKey(w) && w2c.get(w) != c) return false;
        c2w.put(c, w);
        w2c.put(w, c);
    }
    return true;
}

例如 abba 与 "dog cat cat dog" 返回 true；abba 与 "dog cat cat fish" 返回 false；abba 与 "dog dog dog dog" 也返回 false。

完整版教学

一、题目真正考的是双射

“规律匹配”不是简单地看出现次数，而是看每个模式字符是否稳定绑定一个单词，并且每个单词也只能绑定一个模式字符。

pattern = abba
words   = dog cat cat dog
a -> dog
b -> cat

这种关系是双向唯一的，也叫一一对应。

易错点：只要题目说“一一对应”，就要同时防一对多和多对一，单表通常不够。

二、只做单向映射为什么不够

如果只维护 char -> word，下面这个例子会误判：

pattern = abba
words   = dog dog dog dog

单向看：

a -> dog
b -> dog

每个字符都“稳定”映射到同一个单词，但两个不同字符映射到了同一个单词，不符合一一对应。

检查方向	防住的问题
`char -> word`	同一字符对应多个单词
`word -> char`	多个字符抢同一单词
长度相等	模式位和单词位一一对齐

三、双向映射的写法

每轮拿到模式字符 c 和单词 w。先检查旧映射是否冲突，再写入映射。

if (c2w.containsKey(c) && !c2w.get(c).equals(w)) return false;
if (w2c.containsKey(w) && w2c.get(w) != c) return false;

如果两边都不冲突，说明这对关系可以接受；即使之前已经写过，重复 put 也不会改变结果。

四、长度检查必须在前面

pattern.length() 必须等于单词个数，否则根本无法逐位对应。

pattern = "abc"
s = "dog cat"

少一个单词，即使前两位看起来合理，也不能算匹配。

五、字符串切分的细节

题目通常保证单词用单个空格分隔。如果实际工程输入可能有多个空格，split(" ") 会产生空字符串；可以先 trim 再用正则 split("\\s+")。

String[] words = s.trim().split("\\s+");

面试做 LeetCode 原题时按题目约束即可，不要引入不必要复杂度；但被追问工程输入时要能说明差异。

六、复杂度与替代技巧

时间复杂度 O(n)，其中 n 是模式长度或单词数。空间复杂度取决于不同字符和单词数量，最坏 O(n)。

还有一种技巧是用一个哈希表记录“上次出现位置”，把字符和单词映射到同一个下标序列。但双表写法更直观，面试沟通成本低。

abba -> 0,1,1,0
dog cat cat dog -> 0,1,1,0

七、常见误区与追问

误区：只维护 char -> word。 会放过多个模式字符对应同一个单词的情况。
误区：只比较出现次数。 次数相同不代表位置结构和映射关系相同。
误区：忘记先检查长度。 长度不等时不能逐位匹配。
追问：为什么需要双向映射？ 因为题目要求一一对应，而不是多对一或一对多。
追问：多个空格怎么办？ 工程场景用 trim() 和 split("\\s+")，原题按单空格约束即可。
追问：复杂度是多少？ 每个位置处理一次，时间 O(n)，哈希表空间 O(n)。

八、加强记忆

单词规律题要把“模式”翻译成“双射”。一张表防一对多，另一张表防多对一。看到 abba 和 dog cat cat dog，脑子里画成 a->dog, b->cat；再用 dog dog dog dog 提醒自己，单向映射会漏掉多对一。

简化版

详细版