038 · Word Pattern

My First Thoughts

这题应该算是上一题 Isomorphic Strings 的升级版。

上一题是在判断：

字符 -> 字符

这一题只是变成：

字符 -> 单词

所以核心逻辑还是一样的：用字典记录对应关系，并且这个对应关系要保持一对一。真正多出来的步骤，是先把 s 按空格分词。

如果是在 R 里，会直接 split，用空格把 s 分成一个字符串向量。Python 里对应的写法是：

words = s.split(" ")

这个结果是一个 list，例如：

s = "dog cat cat dog"
words = s.split(" ")

得到：

["dog", "cat", "cat", "dog"]

有了这个 words 之后，就可以正常循环了。因为上一题已经写过同构关系，这里可以直接把那套双向映射搬过来，只是把 value 从字符换成单词：

words = s.split(" ")

if len(pattern) != len(words):
    return False

mapping = {}
used = {}

for char, word in zip(pattern, words):
    if char in mapping and mapping[char] != word:
        return False

    if word in used and used[word] != char:
        return False

    mapping[char] = word
    used[word] = char

return True

这里的 mapping 记录的是：

pattern 里的字符 -> s 里的单词

比如：

pattern = "abba"
s = "dog cat cat dog"

就应该记录成：

a -> dog
b -> cat

后面再看到 "b"，它还是要对应 "cat"；再看到 "a"，它还是要对应 "dog"。

used 还是上一题的反向检查：不能让两个不同的 pattern 字符都对应到同一个单词。

所以不需要自己循环找空格然后切片。题目已经说明单词用空格分隔，直接用 split 把输入变成单词 list，才是更自然的预处理。

---

Why That Is Not Enough

这个思路本身已经完整了。和上一题相比，真正需要在代码里额外写清楚的不是双向映射，而是两个输入形态上的细节。

第一个细节是：分词之后，要先检查长度。

比如：

pattern = "abba"
s = "dog cat cat"

pattern 有 4 个字符，但 s 分出来只有 3 个单词。无论后面的映射关系怎么写，都不可能一一对应，所以应该直接返回 False。

如果不先检查长度，而是直接用 zip(pattern, words)，Python 会只遍历较短的那一边。这样最后一个 "a" 根本不会被检查到，容易误判。

第二个细节是：这题的 value 不是单个字符，而是整个单词。

所以变量名最好也跟着换清楚：

• char 表示 pattern 中的当前字符
• word 表示 s 分词后的当前单词
• mapping[char] = word 记录正向关系
• used[word] = char 记录这个单词已经被哪个字符使用

也就是说，算法方向不需要改。只要把“分词结果是 list”“长度必须一致”“value 是整个单词”这几件事写清楚，剩下的就是上一题的同一套双向映射逻辑。

---

Final Idea

先把 s 分成单词 list：

words = s.split(" ")

然后先判断：

len(pattern) == len(words)

如果长度不同，字符和单词数量都对不上，直接返回 False。

接下来沿用上一题的双向映射：

• mapping：记录每个 pattern 字符应该对应哪个单词
• used：记录每个单词已经被哪个 pattern 字符占用

遍历 pattern 和 words 的每一组对应位置：

1. 如果 char 之前出现过，它必须仍然对应当前这个 word
2. 如果 word 之前被用过，它必须仍然来自当前这个 char

只要任意一边冲突，就返回 False。全部检查完都没有冲突，就返回 True。

---

Why It Works

题目要求的是一种一对一的模式关系。

正向看，同一个 pattern 字符不能一会儿对应 "dog"，一会儿对应 "fish"。所以需要 mapping 来保证每个字符的对应单词稳定。

反向看，不同 pattern 字符也不能都对应同一个单词。比如：

pattern = "abba"
s = "dog dog dog dog"

如果只看正向，每个字符自己的对应关系都很稳定：

a -> dog
b -> dog

但这不是一对一关系，因为 "dog" 同时被 "a" 和 "b" 使用了。used 正好负责检查这种反向冲突。

长度检查保证了每个 pattern 字符都有一个单词可以对应，也保证没有多余单词。双向映射保证了对应关系既稳定又不重复占用。两部分合在一起，就完整表达了题目的模式要求。

---

Code

def wordPattern(pattern, s):
    words = s.split(" ")

    if len(pattern) != len(words):
        return False

    mapping = {}
    used = {}

    for char, word in zip(pattern, words):
        if char in mapping and mapping[char] != word:
            return False

        if word in used and used[word] != char:
            return False

        mapping[char] = word
        used[word] = char

    return True

---

Complexity

Time	\(O(n)\) - n 是 s 的长度；分词需要遍历字符串，之后每个单词和 pattern 字符各检查一次
Space	\(O(n)\) - words 会保存分词结果，两个字典也会记录出现过的字符和单词

---

Takeaway

当新题只是把“比较单位”从字符换成单词时，先把输入转换成适合比较的结构，再复用原来的关系判断。这里的关键不是手写切片，而是先 split 成单词 list，再做一对一映射检查。

---

← Quiz