单词规律 图解题解

这道题到底在问什么

pattern

"abba"

s

"dog cat cat dog"

输出

true

解释

a↔dog, b↔cat，前后一致

最优解：一步一步想明白

1. 3不够! 比如 pattern=ab、s=dog dog：只看「字母→单词」，a→dog、b→dog 都没矛盾，会误判成 true。但 dog 同时被 a 和 b 占了，违反一一对应。所以必须两个方向都记。
2. 4也能做：把相同字母的下标聚成组、相同单词的下标聚成组，再看两套分组是否一模一样。但要建两套分组结构、再逐组比对，写起来啰嗦。其实一遍扫就够了。
3. 5核心：一边扫一边记两份对应。c2w 管「字母指向哪个单词」，w2c 管「单词指向哪个字母」。两张表互相把关，任何一边和历史记录打架就立刻 false。
4. 6对每一对字母-单词 (c, w)：① c 之前记过且记的不是 w → 矛盾 false；② w 之前记过且记的不是 c → 矛盾 false；都过关就把 c→w、w→c 各登记一次。扫完没翻车就是 true。
5. 7pattern 4 字母 · s 切出 4 个单词把 s 按空格切成单词表 [dog, cat, cat, dog]，正好 4 个，和 pattern 的 4 个字母一一对齐(格子下方小数字是下标)。下面会逐对处理，并在底下长出 c2w / w2c 两张哈希表。
6. 8len(pattern)=4 == 单词数=4第一道关：字母个数必须等于单词个数。这里都是 4，过关(全亮)。如果一句话单词比字母多或少，根本对不上，直接 false。
7. 9a↔dog, b↔cat提前剧透结果：扫完后字母 a(下标0、3)全程对 dog、b(下标1、2)全程对 cat，反过来也成立，没有任何冲突。下面看两张表怎么一对一对建起来。
8. 10c2w 查 a → 空第一对：字母 a(下标0) 配单词 dog。先查正向表 c2w：里头没有 a，说明 a 还没被绑定，先放行。
9. 11w2c 查 dog → 空再查反向表 w2c(切到单词→字母这张)：dog 也没被任何字母占用。两个方向都查过、都是空的，这一对可以放心登记。
10. 12c2w[a]=dog · w2c[dog]=a都没冲突，两个方向各登记一次：c2w 加「a → dog」(绿色高亮)，w2c 同步记「dog → a」。下标0 锁定，a 和 dog 绑死。
11. 13c2w 查 b → 空第二对：字母 b(下标1) 配 cat。查正向 c2w，只有 a→dog 那行，没有 b，b 还是新的。
12. 14w2c 查 cat → 空切到反向表 w2c：现在它有 dog→a 一行，查 cat 没有，说明 cat 还没被占用。两边都查空，这对可登记。
13. 15c2w[b]=cat · w2c[cat]=b登记第二组：c2w 新增「b → cat」(高亮)，w2c 同步记「cat → b」。下标0、1 都锁定，a、b 各有归属。
14. 16c2w[b]=cat == cat第三对又是 b(下标2) 配 cat。查正向 c2w：b 已经在(蓝色高亮)，记的是 cat，正好等于当前单词——正向一致。
15. 17w2c[cat]=b == b再查反向 w2c：cat 这行(高亮)记的是 b，也正好等于当前字母。两个方向都对得上，记录已存在且一致，无需新增。
16. 18已存在且一致 · 继续因为 b、cat 早绑好了，这对只是复查通过，两张表不动，下标2 确认对齐(已点亮 0、1、2)。这正是「同字母必须对同单词」。
17. 19c2w[a]=dog == dog最后一对 a(下标3) 配 dog。查正向 c2w：a 那行(高亮)记的是 dog，等于当前单词——正向一致。
18. 20w2c[dog]=a == a查反向 w2c：dog 这行(高亮)记的是 a，等于当前字母。两方向都对得上，最后一对也复查通过。
19. 21返回 true四对都没翻车(下标 0、1、2、3 全亮)，两张表最终是 a↔dog、b↔cat 的干净双向映射。返回 true，和示例答案完全对上。
20. 22把最后一个单词换成 fish 看看会怎样。前三对和刚才完全一样(a→dog, b→cat, b→cat 复查通过)，问题出在最后一对。
21. 23a→dog, b→cat 已建反例 s="dog cat cat fish"：头两对 (a,dog)、(b,cat) 跟正例一模一样，两张表照常建起 a→dog、b→cat(下标0、1 点亮)。问题还没暴露。
22. 24和正例一致第三对还是 (b, cat)，和正例一样复查通过(下标2 点亮)。三对都没事——坑在最后一对，因为最后一个单词被换成了 fish。
23. 25c2w[a]=dog ≠ fish最后一对是 a 配 fish。查 c2w 发现 a 早就绑死 dog(高亮行)，可现在要它对 fish——同一个字母不能对两个不同单词，直接返回 false。这就是正向表把关的作用。
24. 26前面那个 fish 冲突，单靠正向表就能抓到。但有一种情况只有反向表才拦得住——开头提的 ab/dog dog。下面演给你看。
25. 27c2w[a]=dog · w2c[dog]=apattern=ab、s="dog dog"。第一对 (a, dog) 正常登记：c2w 记 a→dog，反向 w2c 记下 dog→a(关键就在这条反向记录)。
26. 28w2c[dog]=a ≠ b第二对 (b, dog)：正向查 c2w，b 是新的(只看正向会放过!)。但切到反向表 w2c 一查——dog 这行(高亮)早记了 a，dog 已被 a 占用，b 抢不走 → false。这就是必须有反向表的原因。
27. 31一一对应是双向约束：字母不能对多个单词(正向表管)，单词也不能被多个字母占(反向表管)。只记一张会漏掉「不同字母指向同一单词」这种(如 ab→dog dog)，所以两张缺一不可。
28. 33ab 配 "dog dog" 误判如果只建正向 c2w：a→dog、b→dog 各自都没冲突，程序高高兴兴返回 true。可 dog 被两个字母占了，根本不是一一对应。补上反向表 w2c，第二对就会因 dog 已属 a 而正确返回 false。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def wordPattern(self, pattern, s):
        words = s.split()
        if len(pattern) != len(words):
            return False
        c2w, w2c = {}, {}              # 两张哈希表
        for c, w in zip(pattern, words):
            if c in c2w and c2w[c] != w:
                return False
            if w in w2c and w2c[w] != c:
                return False
            c2w[c] = w
            w2c[w] = c
        return True

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        vector<string> words;
        stringstream ss(s);
        string w;
        while (ss >> w) words.push_back(w);
        if (pattern.size() != words.size()) return false;
        unordered_map<char,string> c2w;
        unordered_map<string,char> w2c;
        for (int i = 0; i < (int)pattern.size(); i++) {
            char c = pattern[i]; string ww = words[i];
            if (c2w.count(c) && c2w[c] != ww) return false;
            if (w2c.count(ww) && w2c[ww] != c) return false;
            c2w[c] = ww; w2c[ww] = c;
        }
        return true;
    }
};

class Solution {
    public 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;
    }
}

复杂度

面试官可能追问