290. 单词规律
题目描述
输入一个由小写字母组成的模式串 pattern，以及一个由单词构成、单词之间用一个空格隔开的字符串 s。
判断 s 是否与 pattern 完全匹配。匹配的意思是：pattern 的第 i 个字母对应 s 的第 i 个单词，并且字母和单词之间是一一对应的关系。同一个字母必须总对应同一个单词，不同字母不能对应同一个单词。字母个数和单词个数不相等时也不匹配。
匹配返回 true，否则返回 false。
示例 1
输入：pattern = "abba", s = "dog cat cat dog" 输出：true
解释：a 对应 dog，b 对应 cat，前后一致。
示例 2
输入：pattern = "abba", s = "dog cat cat fish" 输出：false
解释：a 在第 1 位对应 dog，在第 4 位却对应 fish。
示例 3
输入：pattern = "aaaa", s = "dog cat cat dog" 输出：false
解释：a 同时对应了 dog 和 cat 两个不同的单词。
数据范围
1 <= pattern.length <= 300pattern只含小写英文字母。1 <= s.length <= 3000s只含小写英文字母和空格" "。s首尾没有空格。s中相邻单词之间正好隔一个空格。
解题思路
先把 s 按空格切成单词，数量和 pattern 长度不同直接返回 false。之后和「同构字符串」一样用两张哈希表：pw 记录字母 → 单词，wp 记录单词 → 字母。逐对检查，任一方向已有的记录与当前配对不一致就返回 false。
为什么正确
处理完前 i 对后，pw 与 wp 互为逆映射，且前 i 个字母经 pw 映射恰好得到前 i 个单词。
复杂度分析
时间 O(n + m)，n 为 pattern 长度，m 为 s 长度；空间 O(m)。
易错点
只建一张字母 → 单词的表会把 pattern="abba", s="dog dog dog dog" 误判为 true；忘记比较单词数量，则 zip 会悄悄截断多余的部分。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
words = s.split()
if len(words) != len(pattern):
return False
pw, wp = {}, {}
for c, w in zip(pattern, words):
if pw.get(c, w) != w or wp.get(w, c) != c:
return False
pw[c] = w
wp[w] = c
return Trueclass Solution {
public boolean wordPattern(String pattern, String s) {
String[] words = s.trim().split("\\s+");
if (words.length != pattern.length()) {
return false;
}
Map<Character, String> pw = new HashMap<>();
Map<String, Character> wp = new HashMap<>();
for (int i = 0; i < words.length; i++) {
char c = pattern.charAt(i);
String w = words[i];
if (!pw.getOrDefault(c, w).equals(w) || wp.getOrDefault(w, c) != c) {
return false;
}
pw.put(c, w);
wp.put(w, c);
}
return true;
}
}class Solution {
public:
bool wordPattern(string pattern, string s) {
vector<string> words;
stringstream ss(s);
string tok;
while (ss >> tok) words.push_back(tok);
if (words.size() != pattern.size()) {
return false;
}
unordered_map<char, string> pw;
unordered_map<string, char> wp;
for (size_t i = 0; i < pattern.size(); i++) {
char c = pattern[i];
string& w = words[i];
if ((pw.count(c) && pw[c] != w) || (wp.count(w) && wp[w] != c)) {
return false;
}
pw[c] = w;
wp[w] = c;
}
return true;
}
};func wordPattern(pattern string, s string) bool {
words := strings.Fields(s)
if len(words) != len(pattern) {
return false
}
pw, wp := map[byte]string{}, map[string]byte{}
for i := 0; i < len(words); i++ {
c, w := pattern[i], words[i]
if v, ok := pw[c]; ok && v != w {
return false
}
if v, ok := wp[w]; ok && v != c {
return false
}
pw[c] = w
wp[w] = c
}
return true
}var wordPattern = function(pattern, s) {
const words = s.split(' ').filter(w => w.length > 0);
if (words.length !== pattern.length) {
return false;
}
const pw = new Map(), wp = new Map();
for (let i = 0; i < words.length; i++) {
const c = pattern[i], w = words[i];
if ((pw.has(c) && pw.get(c) !== w) || (wp.has(w) && wp.get(w) !== c)) {
return false;
}
pw.set(c, w);
wp.set(w, c);
}
return true;
};function wordPattern(pattern: string, s: string): boolean {
const words = s.split(' ').filter(w => w.length > 0);
if (words.length !== pattern.length) {
return false;
}
const pw = new Map<string, string>(), wp = new Map<string, string>();
for (let i = 0; i < words.length; i++) {
const c = pattern[i], w = words[i];
if ((pw.has(c) && pw.get(c) !== w) || (wp.has(w) && wp.get(w) !== c)) {
return false;
}
pw.set(c, w);
wp.set(w, c);
}
return true;
}