LeetCode 290. 单词规律

2023-10-18 HGNULB 约 8 分钟

文章信息 9 个分类 2 个标签

分类

LeetCode CodeTop 简单未解决 2-5 字节跳动美团阿里巴巴面试经典 150 题

题目描述

✅ 290. 单词规律

题意分析

给一个由小写字母组成的模式串 pattern 和一个由空格分隔的字符串 s，判断 s 是否「遵循」这个模式。遵循的定义是：pattern 中的每个字符与 s 中的每个单词之间存在双射（一一对应）。

「一一对应」是本题唯一的考点，也是最容易漏掉一半的地方。它包含两个方向：同一个字符必须始终对应同一个单词，同一个单词也必须始终对应同一个字符。只检查前者会漏掉「两个不同字符映射到同一个单词」这种情况。

位置是严格对齐的：pattern 的第 i 个字符对应 s 切分出的第 i 个单词。因此长度必须相等，长度不等时无论映射多完美都直接判否。

单词是按空格切分的整体，不能按字符处理；判断两个单词是否相同必须比较内容而不是引用。

边界包括：pattern 长度与单词数不等；同一位置重复出现的字符和单词必须自洽；单个字符对单个单词的最简情形。

解法：双向哈希映射

核心思路

朴素想法是只建一张「字符 → 单词」的表，遍历时检查冲突。这个方向的检查确实能挡住「同一个字符对应了两个不同单词」，比如 pattern 是 ab、s 是 dog dog 时不会被挡住——因为 a 映射 dog、b 映射 dog，两个键各自都没冲突，但 dog 被两个字符共用了，这违反了双射。所以单向表天生有漏洞。

观察到「双射」在数学上等价于「函数 f 是单射且满射到值域」，落到实现上最直接的表达就是同时维护正反两张表：charToWord 和 wordToChar。每读到一对 (c, word)，两边都检查一次，任何一边与已有记录矛盾就立刻返回 false。

由此得到扫描时维护的不变量：处理完前 i 个位置后，两张表共同描述的是一个在已扫描前缀上成立的双射——charToWord 中的每个键值对，在 wordToChar 中都有对称的反向记录，且不存在两个键映射到同一个值。

这条不变量能一直保持，是因为每一步的写入都是成对的：要么两张表都已有一致的记录（什么都不用改），要么两张表都还没有这个键（同时写入一对新的对应）。而「一张表有、另一张表没有」的情形正是冲突，会被检查拦下并直接返回。

还有一个前置条件不能忘：长度不等时必须先返回 false。如果不判长度，pattern 比单词数长会导致下标越界，短则会漏掉后面的单词——比如 pattern 是 a、s 是 dog dog，逐位检查只看第一位会误判为 true。

解题步骤

先按空格把 s 切分成单词数组。用整体切分而不是逐字符扫描，是因为映射的最小单位是单词。

比较 pattern.length() 与单词个数，不等直接返回 false。这一步既是正确性要求（长度不等一定不构成双射），也保证了后面按同一个下标访问两个序列时不会越界。

建两张哈希表：字符到单词、单词到字符。两张表必须同时维护，缺一张就退化成单向映射，漏掉「多个字符共用一个单词」的非法情形。

从左到右遍历每个下标 i，取出字符 c 和单词 word。

若 charToWord 中已有 c 但对应的不是当前 word，返回 false。这挡住「一个字符对应多个单词」。

若 wordToChar 中已有 word 但对应的不是当前 c，返回 false。这挡住「一个单词对应多个字符」，正是单向解法缺失的那一半。

两项检查都通过后，把两个方向的映射都写入。此时无论是新建还是覆盖同值，不变量都继续成立。

遍历结束返回 true，说明整段前缀（即全串）上都满足双射。

以 pattern = "abba"、s = "dog cat cat dog" 走一遍。切分得到 ["dog","cat","cat","dog"]，长度都是 4，通过检查。

i = 0：c = a，word = dog。两张表都为空，无冲突，写入 a→dog、dog→a。

i = 1：c = b，word = cat。charToWord 里没有 b，wordToChar 里没有 cat，写入 b→cat、cat→b。

i = 2：c = b，word = cat。charToWord 中 b 已映射到 cat，与当前一致；wordToChar 中 cat 已映射到 b，也一致。两项检查都通过，重复写入不改变任何内容。

i = 3：c = a，word = dog。同样两边都已有且一致，通过。

遍历结束返回 true。

再用反例 pattern = "abba"、s = "dog dog dog dog" 检验反向表的必要性：i = 0 写入 a→dog、dog→a；i = 1 时 c = b、word = dog，charToWord 里没有 b 这一项，若只查正向表就会误判通过；但 wordToChar 里 dog 已经映射到 a，与当前的 b 不符，第二项检查立刻返回 false。正确答案确实是 false——两个不同字符不能共用同一个单词。

代码实现

class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] words = s.split(" ");
        if (pattern.length() != words.length) {
            return false;
        }

        Map<Character, String> charToWord = new HashMap<>();
        Map<String, Character> wordToChar = new HashMap<>();

        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            String word = words[i];

            if (charToWord.containsKey(c) && !charToWord.get(c).equals(word)) {
                return false;
            }
            if (wordToChar.containsKey(word) && wordToChar.get(word) != c) {
                return false;
            }

            charToWord.put(c, word);
            wordToChar.put(word, c);
        }

        return true;
    }
}

func wordPattern(pattern string, s string) bool {
    words := strings.Split(s, " ")
    if len(pattern) != len(words) {
        return false
    }

    charToWord := make(map[byte]string)
    wordToChar := make(map[string]byte)

    for i := 0; i < len(pattern); i++ {
        c := pattern[i]
        word := words[i]

        if mappedWord, ok := charToWord[c]; ok && mappedWord != word {
            return false
        }
        if mappedChar, ok := wordToChar[word]; ok && mappedChar != c {
            return false
        }

        charToWord[c] = word
        wordToChar[word] = c
    }

    return true
}

复杂度分析

时间复杂度：$O(n)$，n 是字符串 s 的总长度。切分是一次线性扫描，主循环执行 pattern 长度次，每次的哈希查找与比较摊还与单词长度成正比，累计仍是线性。

空间复杂度：$O(n)$，两张表最多各存下所有不同的字符与单词，切分出的单词数组本身也占线性空间。

关键点总结

判定「一一对应」必须双向检查，单向哈希表只能保证函数性（一个键一个值），保证不了单射（不同键不撞同一个值），这是同构类问题最高频的漏解点。

双向表的写入要成对进行，检查也要成对进行，这样才能维持「两张表互为逆映射」的不变量；只写一边会让后续检查失效。

长度校验要放在循环之前，它同时承担正确性与防越界两项职责，是这类「两个序列按位对齐」题目的标准第一步。

除了双向表，还有一种等价写法：把两个序列都转换成「首次出现位置」的规范序列（如 abba 与 dog cat cat dog 都转成 0,1,1,0）再比较，代码更短且天然对称，值得掌握。

面试视角：面试官通常在你写完单向表后直接给出 pattern = "abba", s = "dog dog dog dog" 让你自己发现漏洞，能提前主动说出这个反例会显著加分；再追问时可以补充 Java 里必须用 equals 比较字符串、以及 Character 与 char 自动拆箱在超出缓存范围时的坑。

易错点总结

错误写法：只建「字符 → 单词」一张表 → 用例 pattern = "abba", s = "dog dog dog dog"，两个字符各自没冲突，返回 true，正确答案是 false。

错误写法：只建「单词 → 字符」一张表 → 用例 pattern = "aaaa", s = "dog cat cat dog"，每个单词都只对应字符 a 没有冲突，返回 true，正确答案是 false。

错误写法：漏掉长度校验 → 用例 pattern = "a", s = "dog dog"，只检查第一位就返回 true，正确答案是 false；反过来 pattern = "aa", s = "dog" 会直接数组越界异常。

错误写法：Java 里用 == 比较两个单词，如 charToWord.get(c) != word → 用例 pattern = "ab", s = "dog cat" 里字面量可能命中常量池碰巧正确，但一旦单词来自 split 的新对象，比较的是引用地址，pattern = "aa", s = "dog dog" 会被误判为 false。

错误写法：Java 里把 wordToChar 的值取成 Character 后用 != 比较且字符超出缓存范围 → 本题字符都是小写字母落在缓存内不会出错，但同样写法用在 int 值上（超过 127）会因为装箱对象不同而误判。

错误写法：先写入映射再做冲突检查 → 用例 pattern = "abba", s = "dog dog dog dog"，第 1 位写入后 dog 的映射被 b 覆盖，检查时反而看不出冲突，返回 true。

错误写法：用 s.split("\\s+") 或先 trim 再切分 → 用例 pattern = "ab", s = "dog cat"（两个空格），按题意应切出三段而判 false，宽松切分会得到两段并返回 true。

错误写法：把 s 按字符遍历而不是按单词 → 用例 pattern = "abba", s = "dog cat cat dog"，字符数远多于模式长度，长度校验直接失败返回 false，正确答案是 true。

错误写法：只统计字符种类数与单词种类数是否相等 → 用例 pattern = "abab", s = "dog cat cat dog"，两边都是 2 种，返回 true，但位置对不上，正确答案是 false。

错误写法：认为映射只需在首次出现时建立、后续不再检查 → 用例 pattern = "aba", s = "dog cat fish"，第 2 位的 a 本该对应 dog 却是 fish，跳过检查就会返回 true。

错误写法：Go 里用 charToWord[c] != word 而不判断键是否存在 → 用例 pattern = "ab", s = "dog cat"，未赋值的键返回零值空串，与 word 不等而直接返回 false，正确答案是 true。

相似题目

题目	难度	考察点
205. 同构字符串	简单	映射单位从单词降为字符，可用两个 256 长的数组代替哈希表
242. 有效的字母异位词	简单	只比较字符频次而不关心位置，是「无序对应」的对照组
49. 字母异位词分组	中等	需要为每组构造规范签名作为哈希键，考察键的设计
面试题 01.02. 判定是否互为字符重排	简单	同为频次比较，但字符集扩展到 ASCII，计数数组要开到 128
389. 找不同	简单	只有一个字符差异，可用异或把空间降到 $O(1)$
953. 验证外星语词典	简单	建的是字符到序号的映射表，之后按自定义顺序做逐位比较