LeetCode 290. 单词规律

◎

本节目标

将同构映射从字符推广到模式字符与单词之间的一一对应。

这道题是单词与映射解题框架中双向映射的推广：左侧元素是模式字符，右侧元素是从空白分割得到的单词。

查看原题

朴素思路及瓶颈

可以让每个模式位置回看此前所有位置，检查字符相等是否恰好对应单词相等，最坏为 O(n²)。先把句子提取为单词数组，再维护两张映射，就能将每个位置的验证降为常数次哈希查询。

词数与双向映射不变量

首先，模式长度必须等于单词数；否则不存在完整配对。随后正向表保证一个模式字符不会对应多个单词，反向表保证不同模式字符不会共享同一个单词。若只检查正向表，abba 与 dog dog dog dog 会被错误接受：a -> dog、b -> dog 各自稳定，却不是一一对应。

代码实现

两种实现先按空白提取单词、检查词数，然后同步维护 pattern -> word 与 word -> pattern。因此连续空格不会产生空单词，也不会改变配对单位。

C++

C++17

#include <sstream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        istringstream parser(s);
        vector<string> words;
        string word;
        while (parser >> word) {
            words.push_back(word);
        }
        if (pattern.size() != words.size()) {
            return false;
        }

        unordered_map<char, string> forward;
        unordered_map<string, char> backward;
        for (size_t index = 0; index < pattern.size(); index++) {
            char symbol = pattern[index];
            const string& current = words[index];
            if ((forward.count(symbol) && forward[symbol] != current) ||
                (backward.count(current) && backward[current] != symbol)) {
                return false;
            }
            forward[symbol] = current;
            backward[current] = symbol;
        }
        return true;
    }
};

Python

Python 3

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split()
        if len(pattern) != len(words):
            return False

        forward: dict[str, str] = {}
        backward: dict[str, str] = {}
        for symbol, word in zip(pattern, words):
            if symbol in forward and forward[symbol] != word:
                return False
            if word in backward and backward[word] != symbol:
                return False
            forward[symbol] = word
            backward[word] = symbol
        return True

复杂度分析

• 时间复杂度：O(n)，其中 n 包含输入字符扫描与模式位置处理。
• 空间复杂度：O(k)，k 是不同模式字符和不同单词数。

易错点

• 直接以单个空格切割，导致连续空白产生额外空单词。
• 未检查词数就按模式索引单词。
• 只检查模式字符到单词的单向映射，错误接受多对一关系。

模式迁移

模式字符可以替换为任意分类标签，单词可替换为路径段、事件类型或对象标识。只要约束仍是一一对应，就保留双向映射；若允许多个左侧共享右侧，再明确移除反向不变量。