LeetCode 第290题：单词规律

📖 文章摘要

本文详细解析LeetCode第290题“单词规律”，这是一道考察字符串处理和哈希表应用的中等难度题目。文章提供了哈希表映射和双向映射两种实现方案，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合学习字符串处理和哈希表应用的读者。

核心知识点： 字符串处理、哈希表、双向映射
难度等级： 中等
推荐人群： 具备基础算法知识，想要提升字符串处理和哈希表应用能力的开发者

题目描述

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

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

示例

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

输入: pattern = "abba", str = "dog dog dog dog"
输出: false

提示

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

解题思路

本题可以使用两种方法来实现：

哈希表映射：
- 使用两个哈希表分别记录pattern到word和word到pattern的映射
- 遍历pattern和str，检查映射关系是否一致
- 如果出现不一致，返回false
双向映射：
- 使用一个哈希表记录pattern到word的映射
- 使用一个集合记录已经映射的word
- 遍历pattern和str，检查映射关系是否一致
- 如果出现不一致，返回false

图解思路

哈希表映射示例

pattern	str	映射关系
a	dog	a -> dog
b	cat	b -> cat
b	cat	检查一致
a	dog	检查一致

双向映射示例

pattern	str	映射	已用单词
a	dog	a -> dog	{dog}
b	cat	b -> cat	{dog, cat}
b	cat	检查一致	{dog, cat}
a	dog	检查一致	{dog, cat}

代码实现

C# 实现

public class Solution {
    public bool WordPattern(string pattern, string str) {
        string[] words = str.Split(' ');
        if (pattern.Length != words.Length) return false;
        
        Dictionary<char, string> charToWord = new Dictionary<char, string>();
        Dictionary<string, char> wordToChar = new Dictionary<string, char>();
        
        for (int i = 0; i < pattern.Length; i++) {
            char c = pattern[i];
            string word = words[i];
            
            if (!charToWord.ContainsKey(c)) {
                if (wordToChar.ContainsKey(word)) return false;
                charToWord[c] = word;
                wordToChar[word] = c;
            } else if (charToWord[c] != word) {
                return false;
            }
        }
        
        return true;
    }
}

Python 实现

class Solution:
    def wordPattern(self, pattern: str, str: str) -> bool:
        words = str.split()
        if len(pattern) != len(words):
            return False
            
        char_to_word = {}
        word_to_char = {}
        
        for c, word in zip(pattern, words):
            if c not in char_to_word:
                if word in word_to_char:
                    return False
                char_to_word[c] = word
                word_to_char[word] = c
            elif char_to_word[c] != word:
                return False
                
        return True

C++ 实现

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        vector<string> words;
        stringstream ss(str);
        string word;
        
        while (ss >> word) {
            words.push_back(word);
        }
        
        if (pattern.length() != words.size()) {
            return false;
        }
        
        unordered_map<char, string> charToWord;
        unordered_map<string, char> wordToChar;
        
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern[i];
            string word = words[i];
            
            if (charToWord.find(c) == charToWord.end()) {
                if (wordToChar.find(word) != wordToChar.end()) {
                    return false;
                }
                charToWord[c] = word;
                wordToChar[word] = c;
            } else if (charToWord[c] != word) {
                return false;
            }
        }
        
        return true;
    }
};

执行结果

C# 实现

执行用时：88 ms
内存消耗：22.4 MB

Python 实现

执行用时：32 ms
内存消耗：14.2 MB

C++ 实现

执行用时：4 ms
内存消耗：6.4 MB

性能对比

语言	执行用时	内存消耗	特点
C#	88 ms	22.4 MB	代码结构清晰，性能适中
Python	32 ms	14.2 MB	代码最简洁，性能不错
C++	4 ms	6.4 MB	性能最优，内存占用最小

代码亮点

🎯 使用双向映射确保一一对应
💡 使用字典和集合优化查找
🔍 边界检查确保安全访问
🎨 代码结构清晰，易于维护

常见错误分析

🚫 未处理长度不匹配情况
🚫 未检查双向映射关系
🚫 字符串分割处理不当
🚫 未考虑重复映射问题

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
哈希表映射	O(n)	O(n)	实现简单	需要两个哈希表
双向映射	O(n)	O(n)	空间效率高	实现稍复杂

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第290题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

示例 3：

示例 4：

提示

解题思路

图解思路

哈希表映射示例

双向映射示例

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流