《程序员面试金典（第6版）》面试题 16.18. 模式匹配（暴力破解 + 剪枝）

题目描述

你有两个字符串，即pattern和value。 pattern字符串由字母"a"和"b"组成，用于描述字符串中的模式。
例如，字符串"catcatgocatgo"匹配模式"aabab"（其中"cat"是"a"，“go"是"b”），
该字符串也匹配像"a"、"ab"和"b"这样的模式。
但需注意"a"和"b"不能同时表示相同的字符串。编写一个方法判断value字符串是否匹配pattern字符串。

示例 1：

输入： pattern = "abba", value = "dogcatcatdog"
输出： true

示例 2：

输入： pattern = "abba", value = "dogcatcatfish"
输出： false

示例 3：

输入： pattern = "aaaa", value = "dogcatcatdog"
输出： false

示例 4：

输入： pattern = "abba", value = "dogdogdogdog"
输出： true
解释： "a"="dogdog",b=""，反之也符合规则

提示：

• 1 <= len(pattern) <= 1000
• 0 <= len(value) <= 1000
• 你可以假设pattern只包含字母"a"和"b"，value仅包含小写字母。

解题思路与代码（暴力破解 + 剪枝）

这道题的核心其实就只有一个问题。就是如何去用a，b匹配到对应的单词，匹配到返回true，匹配不到返回false。

• 那么如何匹配呢？首先我们要去搞清楚一个问题，那就是a有多少个，b有多少个。
• 这么做的目的是确定a，b在对应的字符串中匹配的范围，为的其实就是在最后匹配的环节中，不要去做无用的匹配。
• 这里我们还有去做一步优化，那就是要使a的数量永远大于等于b。如果a的数量大于b，那么就交换a与b的数量，与模式串中的字符。
• 之后我们用一个for循环，开始划定a匹配字符的范围。a的范围 = value.size() / a的个数。那么b的范围其实就是value剩下的再去除以b的个数。
• 最后我们用一个check函数，去检查字符有没有匹配成功的，如果有，我们就返回true，没有则就是false。

这道题的思路大致上就是这样。其实关于边界范围与具体如何检查我没有细讲。但这其实不算是代码的核心逻辑部分了。只要你用点心也就都能想出来。如果还是有点问题。那就请看我的代码吧~

具体代码如下：

class Solution {
public:bool patternMatching(string pattern, string value) {// 创建两个变量a，b，并且使a的数量永远大于b的数量int aCount = 0;int bCount = 0;for(char &a : pattern)if(a == 'a') ++aCount;else ++bCount;if(aCount < bCount){swap(aCount,bCount);for(char &a : pattern)if(a == 'a') a = 'b';else a = 'a';}if(value.size() == 0) return bCount == 0; for(int i = 0; i * aCount <= value.size(); ++i){ // 先确定模式a匹配的字符范围，剩下的便是b匹配的字符范围int rest = value.size() - aCount * i; // 所有的b平分rest里面的字符if((rest == 0 && bCount == 0) || (bCount != 0 && rest % bCount == 0)){int len_b = (bCount == 0 ? 0 : rest / bCount);if(check(pattern,value,i,len_b)) return true;}}return false;}bool check(string& pattern, string& value, int& aLength, int bLength){string a = "";string b = "";int pos = 0;for(char& c : pattern){if(c == 'a'){string str = value.substr(pos,aLength);if(a.empty()) a = str;else if(a != str) return false;pos += aLength;}else{string str = value.substr(pos,bLength);if(b.empty()) b = str;else if(b != str) return false;pos += bLength;}}return a != b;}
};

总结

这道题目的主要意义在于考察程序员处理字符串模式匹配的能力，以及对算法复杂度优化的理解。

• 字符串模式匹配：这是一个在实际编程中非常常见的问题，例如在文本编辑器的查找和替换功能、正则表达式匹配等场景中都需要处理这类问题。这道题目要求考察者根据给定的模式，找出一个或两个子串（对应模式中的 ‘a’ 和 ‘b’）来使得整个字符串满足该模式，这需要考察者对字符串操作的熟练程度以及对模式匹配问题的理解。

• 算法复杂度优化：这道题目在不进行优化的情况下，最直接的解法可能会涉及到对所有可能的 ‘a’ 和 ‘b’ 的长度组合进行枚举，这会导致时间复杂度过高。因此，考察者需要理解如何通过统计 ‘a’ 和 ‘b’ 的数量、控制 ‘a’ 和 ‘b’ 的长度范围等方法来降低算法的复杂度。

• 边界情况处理：这道题目的输入中 ‘a’ 和 ‘b’ 可以对应空字符串，这增加了问题的复杂性。处理这类问题需要考察者对边界情况的敏感度和处理能力。

综上，这道题目的意义主要在于考察程序员的实际编程能力、对算法复杂度的理解以及对边界情况的处理能力。

最后的最后，如果你觉得我的这篇文章写的不错的话，请给我一个赞与收藏，关注我，我会继续给大家带来更多更优质的干货内容。