力扣面试16.18题解析：模式匹配问题的算法优化与实现（动态规划+字符串匹配）
3个月前 (07-07)
一、题目解读
力扣面试16.18题要求判断字符串value是否可通过替换模式串pattern中的字符"a"和"b"（任意非空子串）进行匹配。例如，模式"aab"可匹配"xxxy"，但无法匹配"xyx"。题目需高效算法判断匹配关系，涉及字符串处理与动态规划思想。
二、解题思路
采用统计+枚举策略：
1. 统计字符数量：计算pattern中a、b出现次数，确保a为多数字符（通过交换优化后续处理）。
2. 空值处理：若value为空，仅当pattern全a或全b时才匹配。
3. 枚举a的长度：遍历a的可能子串长度，计算剩余字符是否可被b均分。
4. 匹配验证：通过滑动窗口逐字符匹配，确保同一字母对应的子串一致。
三、解题步骤
1. 预处理：统计a、b数量并交换，使a占多数，减少分支讨论。
2. 处理空值：快速判断value为空的特例。
3. 枚举长度：从0到value长度除以a次数，计算b子串长度（或0）。
4. 匹配验证：使用双指针分别构建value_a和value_b子串，若发现不一致则终止。
四、代码与注释
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'; // 交换a和b
}
}
// 处理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; // 记录第一个a对应的子串
} 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;
}
}
if (match && pos == value.size()) return true; // 完全匹配成功
}
}
return false;
}
};五、总结
该解法通过统计与枚举结合，巧妙利用字符数量关系减少搜索空间。关键点在于：
1. 交换a、b确保主字符更易处理；
2. 空值特判避免后续逻辑复杂；
3. 滑动窗口匹配子串的一致性。
原创内容 转载请注明出处
