LeetCode 第291题：单词规律 II

📖 文章摘要

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

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

题目描述

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

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

与第290题不同的是，这里的str不需要按空格分割，而是可以任意分割。

示例

示例 1：

输入: pattern = "abab", str = "redblueredblue"
输出: true
解释: 
a -> "red"
b -> "blue"

示例 2：

输入: pattern = "aaaa", str = "asdasdasdasd"
输出: true
解释: 
a -> "asd"

示例 3：

输入: pattern = "aabb", str = "xyzabcxzyabc"
输出: false

提示

1 <= pattern.length <= 20
1 <= str.length <= 50
pattern 只包含小写英文字母
str 只包含小写英文字母

解题思路

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

回溯算法：
- 使用哈希表记录pattern到str的映射
- 使用集合记录已经映射的str子串
- 递归尝试不同的分割方式
- 如果找到一种合法的映射关系，返回true
双向映射：
- 使用两个哈希表分别记录pattern到str和str到pattern的映射
- 递归尝试不同的分割方式
- 如果找到一种合法的映射关系，返回true

图解思路

回溯算法示例

pattern	str	当前映射	已用子串
a	red	a -> red	{red}
b	blue	b -> blue	{red, blue}
a	red	检查一致	{red, blue}
b	blue	检查一致	{red, blue}

状态转换表

状态	操作	结果
初始	尝试第一个字符	建立映射
映射存在	检查是否匹配	继续或回溯
映射不存在	尝试新的映射	继续或回溯
全部匹配	返回true	成功
无法匹配	返回false	失败

代码实现

C# 实现

public class Solution {
    public bool WordPatternMatch(string pattern, string str) {
        Dictionary<char, string> charToStr = new Dictionary<char, string>();
        HashSet<string> used = new HashSet<string>();
        return Backtrack(pattern, 0, str, 0, charToStr, used);
    }
    
    private bool Backtrack(string pattern, int pIndex, string str, int sIndex, 
                          Dictionary<char, string> charToStr, HashSet<string> used) {
        if (pIndex == pattern.Length && sIndex == str.Length) return true;
        if (pIndex == pattern.Length || sIndex == str.Length) return false;
        
        char c = pattern[pIndex];
        
        // 如果当前字符已经有映射
        if (charToStr.ContainsKey(c)) {
            string mapped = charToStr[c];
            if (!str.Substring(sIndex).StartsWith(mapped)) return false;
            return Backtrack(pattern, pIndex + 1, str, sIndex + mapped.Length, 
                           charToStr, used);
        }
        
        // 尝试所有可能的分割
        for (int i = sIndex; i < str.Length; i++) {
            string substr = str.Substring(sIndex, i - sIndex + 1);
            if (used.Contains(substr)) continue;
            
            charToStr[c] = substr;
            used.Add(substr);
            
            if (Backtrack(pattern, pIndex + 1, str, i + 1, charToStr, used)) {
                return true;
            }
            
            charToStr.Remove(c);
            used.Remove(substr);
        }
        
        return false;
    }
}

Python 实现

class Solution:
    def wordPatternMatch(self, pattern: str, str: str) -> bool:
        char_to_str = {}
        used = set()
        
        def backtrack(p_index: int, s_index: int) -> bool:
            if p_index == len(pattern) and s_index == len(str):
                return True
            if p_index == len(pattern) or s_index == len(str):
                return False
                
            c = pattern[p_index]
            
            # 如果当前字符已经有映射
            if c in char_to_str:
                mapped = char_to_str[c]
                if not str[s_index:].startswith(mapped):
                    return False
                return backtrack(p_index + 1, s_index + len(mapped))
            
            # 尝试所有可能的分割
            for i in range(s_index, len(str)):
                substr = str[s_index:i + 1]
                if substr in used:
                    continue
                    
                char_to_str[c] = substr
                used.add(substr)
                
                if backtrack(p_index + 1, i + 1):
                    return True
                    
                del char_to_str[c]
                used.remove(substr)
            
            return False
        
        return backtrack(0, 0)

C++ 实现

class Solution {
private:
    bool backtrack(const string& pattern, int pIndex, const string& str, int sIndex,
                  unordered_map<char, string>& charToStr, unordered_set<string>& used) {
        if (pIndex == pattern.length() && sIndex == str.length()) return true;
        if (pIndex == pattern.length() || sIndex == str.length()) return false;
        
        char c = pattern[pIndex];
        
        // 如果当前字符已经有映射
        if (charToStr.find(c) != charToStr.end()) {
            string mapped = charToStr[c];
            if (str.substr(sIndex).find(mapped) != 0) return false;
            return backtrack(pattern, pIndex + 1, str, sIndex + mapped.length(),
                           charToStr, used);
        }
        
        // 尝试所有可能的分割
        for (int i = sIndex; i < str.length(); i++) {
            string substr = str.substr(sIndex, i - sIndex + 1);
            if (used.find(substr) != used.end()) continue;
            
            charToStr[c] = substr;
            used.insert(substr);
            
            if (backtrack(pattern, pIndex + 1, str, i + 1, charToStr, used)) {
                return true;
            }
            
            charToStr.erase(c);
            used.erase(substr);
        }
        
        return false;
    }
    
public:
    bool wordPatternMatch(string pattern, string str) {
        unordered_map<char, string> charToStr;
        unordered_set<string> used;
        return backtrack(pattern, 0, str, 0, charToStr, used);
    }
};

执行结果

C# 实现

执行用时：156 ms
内存消耗：35.2 MB

Python 实现

执行用时：132 ms
内存消耗：16.8 MB

C++ 实现

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

性能对比

语言	执行用时	内存消耗	特点
C#	156 ms	35.2 MB	代码结构清晰，性能适中
Python	132 ms	16.8 MB	代码最简洁，性能不错
C++	48 ms	14.2 MB	性能最优，内存占用最小

代码亮点

🎯 使用回溯算法处理所有可能的分割
💡 使用哈希表和集合优化查找
🔍 边界检查确保安全访问
🎨 代码结构清晰，易于维护

常见错误分析

🚫 未处理所有可能的分割情况
🚫 未检查双向映射关系
🚫 字符串分割处理不当
🚫 未考虑重复映射问题

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
回溯算法	O(n^m)	O(n)	实现简单	时间复杂度高
双向映射	O(n^m)	O(n)	空间效率高	实现稍复杂

📖 系列导航

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

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

💬 互动交流

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

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

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

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

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

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

示例 3：

提示

解题思路

图解思路

回溯算法示例

状态转换表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流