力扣面试16.18题解析:模式匹配问题的算法优化与实现(动态规划+字符串匹配)
一、题目解读
力扣面试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. 滑动窗口匹配子串的一致性。
原创内容 转载请注明出处