LeetCode 290: Word Pattern (Bidirectional Hash Mapping Consistency)
LeetCode 290Hash TableStringToday we solve LeetCode 290 - Word Pattern.
Source: https://leetcode.com/problems/word-pattern/
English
Problem Summary
Given a pattern string and a space-separated sentence, determine whether the sentence follows the same pattern. Each pattern character must map to exactly one word, and each word must map back to exactly one character.
Key Insight
This is a bijection check, not only a one-way mapping. We must enforce both char -> word and word -> char consistency at every index.
Brute Force and Limitations
Brute force tries all assignments/backtracking, but that is unnecessary. Since each position gives a direct constraint, linear scanning with two hash maps is enough.
Optimal Algorithm Steps (Two-Map Bijection Check)
1) Split sentence by spaces into words.
2) If word count != pattern length, return false.
3) For each index i, let c = pattern[i], w = words[i].
4) If existing mappings conflict in either direction, return false.
5) Otherwise record both mappings and continue.
6) End of loop means pattern is valid.
Complexity Analysis
Time: O(n), where n is number of words/characters.
Space: O(k), where k is number of distinct chars/words.
Common Pitfalls
- Only checking char -> word and forgetting reverse mapping.
- Not checking length mismatch early.
- Incorrect split behavior when multiple spaces are possible (LeetCode input is normalized).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public boolean wordPattern(String pattern, String s) {
String[] words = s.split(" ");
if (words.length != pattern.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;
}
}func wordPattern(pattern string, s string) bool {
words := strings.Split(s, " ")
if len(words) != len(pattern) {
return false
}
c2w := map[byte]string{}
w2c := map[string]byte{}
for i := 0; i < len(pattern); i++ {
c := pattern[i]
w := words[i]
if v, ok := c2w[c]; ok && v != w {
return false
}
if v, ok := w2c[w]; ok && v != c {
return false
}
c2w[c] = w
w2c[w] = c
}
return true
}class Solution {
public:
bool wordPattern(string pattern, string s) {
vector<string> words;
string cur;
stringstream ss(s);
while (ss >> cur) words.push_back(cur);
if (words.size() != pattern.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];
const string& w = words[i];
if (c2w.count(c) && c2w[c] != w) return false;
if (w2c.count(w) && w2c[w] != c) return false;
c2w[c] = w;
w2c[w] = c;
}
return true;
}
};class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
words = s.split(" ")
if len(words) != len(pattern):
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 Truevar wordPattern = function(pattern, s) {
const words = s.split(" ");
if (words.length !== pattern.length) return false;
const c2w = new Map();
const w2c = new Map();
for (let i = 0; i < pattern.length; i++) {
const c = pattern[i];
const w = words[i];
if (c2w.has(c) && c2w.get(c) !== w) return false;
if (w2c.has(w) && w2c.get(w) !== c) return false;
c2w.set(c, w);
w2c.set(w, c);
}
return true;
};中文
题目概述
给定模式串 pattern 和空格分隔字符串 s，判断 s 是否遵循该模式：每个字符唯一映射到一个单词，且每个单词也唯一映射回一个字符。
核心思路
本质是双向一一映射（bijection）校验。只做单向 字符 -> 单词 不够，还要同时维护 单词 -> 字符。
基线解法与不足
可以把它当作“分配映射”的搜索问题，但没必要回溯。每一位的约束是确定性的，线性扫描 + 双哈希表即可完成。
最优算法步骤（双哈希映射一致性）
1）按空格拆分 s 得到单词数组。
2）若单词数与模式长度不同，直接返回 false。
3）遍历每个位置 i，取 c = pattern[i]、w = words[i]。
4）若任一方向已有映射但与当前不一致，返回 false。
5）否则写入两张映射表并继续。
6）遍历结束仍无冲突则返回 true。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(k)（不同字符/单词个数）。
常见陷阱
- 只检查字符到单词，不检查单词到字符。
- 忘记先做长度不等的快速失败。
- 分词处理不一致（本题输入通常是单空格规范格式）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public boolean wordPattern(String pattern, String s) {
String[] words = s.split(" ");
if (words.length != pattern.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;
}
}func wordPattern(pattern string, s string) bool {
words := strings.Split(s, " ")
if len(words) != len(pattern) {
return false
}
c2w := map[byte]string{}
w2c := map[string]byte{}
for i := 0; i < len(pattern); i++ {
c := pattern[i]
w := words[i]
if v, ok := c2w[c]; ok && v != w {
return false
}
if v, ok := w2c[w]; ok && v != c {
return false
}
c2w[c] = w
w2c[w] = c
}
return true
}class Solution {
public:
bool wordPattern(string pattern, string s) {
vector<string> words;
string cur;
stringstream ss(s);
while (ss >> cur) words.push_back(cur);
if (words.size() != pattern.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];
const string& w = words[i];
if (c2w.count(c) && c2w[c] != w) return false;
if (w2c.count(w) && w2c[w] != c) return false;
c2w[c] = w;
w2c[w] = c;
}
return true;
}
};class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
words = s.split(" ")
if len(words) != len(pattern):
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 Truevar wordPattern = function(pattern, s) {
const words = s.split(" ");
if (words.length !== pattern.length) return false;
const c2w = new Map();
const w2c = new Map();
for (let i = 0; i < pattern.length; i++) {
const c = pattern[i];
const w = words[i];
if (c2w.has(c) && c2w.get(c) !== w) return false;
if (w2c.has(w) && w2c.get(w) !== c) return false;
c2w.set(c, w);
w2c.set(w, c);
}
return true;
};
Comments