What is the main idea behind Word Pattern?

The main idea is enforcing a bijection between pattern letters and words. A valid solution must make repeated letters reuse the same word and must also block two different letters from mapping to one word.

Why is one hash map not enough for Word Pattern?

A single character-to-word map catches when one letter changes words, but it misses word reuse by a different letter. You need the reverse check as well, either with a second map or with a used-word structure.

What should I check before building mappings?

First split s into words and compare the word count with pattern.length. If they differ, Word Pattern cannot be valid because the mapping must cover every position exactly once.

Is Word Pattern a hash table problem or a string problem?

It is both. The string part is tokenizing s into words correctly, and the hash table part is enforcing the one-to-one mapping without collisions.

What makes pattern = "aaaa" and s = "dog cat cat dog" false?

The letter a appears at every position, so it must map to one single word everywhere. Seeing dog first and cat later breaks that consistency immediately, so the answer is false.

#290

Easy

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

单词规律

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。这里的遵循指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。具体来说： pattern 中的每个字母都恰好映射到 s 中的一个唯一单词。 s 中的每个唯…

哈希表字符串

题目描述

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的遵循指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。具体来说：

pattern 中的每个字母都恰好映射到 s 中的一个唯一单词。
s 中的每个唯一单词都恰好映射到 pattern 中的一个字母。
没有两个字母映射到同一个单词，也没有两个单词映射到同一个字母。

示例1:

输入: pattern = "abba", s = "dog cat cat dog"
输出: true

示例 2:

输入:pattern = "abba", s = "dog cat cat fish"
输出: false

示例 3:

输入: pattern = "aaaa", s = "dog cat cat dog"
输出: false

提示:

1 <= pattern.length <= 300
pattern 只包含小写英文字母
1 <= s.length <= 3000
s 只包含小写英文字母和 ' '
s 不包含 任何前导或尾随对空格
s 中每个单词都被 单个空格 分隔

lightbulb

解题思路

方法一：哈希表

我们先将字符串 $s$ 按照空格分割成单词数组 $ws$ ，如果 $pattern$ 和 $ws$ 的长度不相等，直接返回 false。否则，我们使用两个哈希表 $d_1$ 和 $d_2$ ，分别记录 $pattern$ 和 $ws$ 中每个字符和单词的对应关系。

接下来，我们遍历 $pattern$ 和 $ws$ ，对于每个字符 $a$ 和单词 $b$ ，如果 $d_1$ 中存在 $a$ 的映射，且映射的单词不是 $b$ ，或者 $d_2$ 中存在 $b$ 的映射，且映射的字符不是 $a$ ，则返回 false。否则，我们将 $a$ 和 $b$ 的映射分别加入 $d_1$ 和 $d_2$ 中。

遍历结束后，返回 true。

时间复杂度 $O(m + n)$ ，空间复杂度 $O(m + n)$ 。其中 $m$ 和 $n$ 分别是 $pattern$ 和字符串 $s$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        ws = s.split()
        if len(pattern) != len(ws):
            return False
        d1 = {}
        d2 = {}
        for a, b in zip(pattern, ws):
            if (a in d1 and d1[a] != b) or (b in d2 and d2[b] != a):
                return False
            d1[a] = b
            d2[b] = a
        return True

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They want you to say "bijection" or explicitly explain why checking only character-to-word mapping is insufficient.
question_mark
They expect an early length check after splitting, because Word Pattern requires every pattern position to match one word.
question_mark
They may probe whether two different letters can map to the same word, which reveals whether you handled the reverse mapping.

warning

常见陷阱

外企场景

error
Using only one hash map and accidentally accepting cases where two pattern letters share one word.
error
Forgetting to compare word count against pattern length before building mappings.
error
Treating this like substring matching instead of exact token-by-token word matching separated by spaces.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the actual mapping for Word Pattern instead of only true or false.
arrow_right_alt
Handle an input where words are streamed one by one instead of pre-splitting the full string.
arrow_right_alt
Generalize the same bijection check to pattern tokens and sentence tokens beyond single characters and lowercase words.

help

常见问题

外企场景

继续练习

#299 猜数字游戏 #336 回文对 #242 有效的字母异位词