力扣面试16.18题解：模式匹配问题的完整实现指南

一、问题描述

给定一个模式字符串pattern和一个值字符串value，判断value是否能够匹配pattern。模式由字母a和b组成，表示一种字符串模式，其中a和b分别表示不同的子字符串。

二、算法核心思想

本解决方案采用枚举和验证的方法：

1. 统计模式中a和b的出现次数

2. 确保a是出现次数较多的字符以简化处理

3. 处理特殊边界情况（空字符串）

4. 枚举a可能的长度并计算对应的b长度

5. 验证每种可能的长度组合是否匹配

三、完整代码实现（带详细注释）

class Solution {
public:
    bool patternMatching(string pattern, string value) {
        // 统计pattern中a和b的数量
        int count_a = 0, count_b = 0;
        for (char c : pattern) {
            if (c == 'a') count_a++;
            else count_b++;
        }
        
        // 确保a是出现次数较多的字符，简化后续处理
        if (count_a < count_b) {
            swap(count_a, count_b);
            for (char& c : pattern) {
                c = (c == 'a') ? 'b' : 'a';
            }
        }
        
        // 处理value为空的情况
        if (value.empty()) {
            return count_b == 0; // 只有全a或全b的模式可以匹配空字符串
        }
        
        // 枚举a可能的长度
        for (int len_a = 0; len_a <= value.size() / count_a; ++len_a) {
            int remaining = value.size() - count_a * len_a;
            // 检查b的长度是否有效
            if ((count_b == 0 && remaining == 0) || 
                (count_b != 0 && remaining % count_b == 0)) {
                int len_b = (count_b == 0) ? 0 : remaining / count_b;
                
                // 尝试匹配
                int pos = 0;
                string value_a, value_b;
                bool match = true;
                
                for (char c : pattern) {
                    if (c == 'a') {
                        string sub = value.substr(pos, len_a);
                        if (value_a.empty()) {
                            value_a = sub;
                        } else if (value_a != sub) {
                            match = false;
                            break;
                        }
                        pos += len_a;
                    } else {
                        string sub = value.substr(pos, len_b);
                        if (value_b.empty()) {
                            value_b = sub;
                        } else if (value_b != sub) {
                            match = false;
                            break;
                        }
                        pos += len_b;
                    }
                }
                
                // 检查a和b不能表示相同字符串
                if (match && value_a != value_b) {
                    return true;
                }
            }
        }
        return false;
    }
};

四、算法分步解析

1. 统计阶段：

• 统计模式中a和b的出现次数

• 确保a是出现次数较多的字符

2. 边界处理：

• 处理value为空字符串的特殊情况

3. 枚举阶段：

• 枚举a可能的长度

• 计算对应的b长度

• 检查长度组合的有效性

4. 验证阶段：

• 尝试每种可能的长度组合

• 验证是否匹配整个字符串

• 确保a和b表示不同的子字符串

五、常见误区与调试技巧

1. 忘记处理模式全为a或全为b的情况

2. 没有正确处理空字符串的情况

3. 枚举长度时边界条件错误

4. 忘记验证a和b不能表示相同字符串

六、扩展思考

1. 如果模式包含更多字符（如a,b,c）该如何处理？

2. 如何优化算法以减少时间复杂度？

3. 如何处理包含通配符的模式？