题目描述
示例 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有多少个。
- 这么做的目的是确定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’ 可以对应空字符串，这增加了问题的复杂性。处理这类问题需要考察者对边界情况的敏感度和处理能力。
综上，这道题目的意义主要在于考察程序员的实际编程能力、对算法复杂度的理解以及对边界情况的处理能力。
最后的最后，如果你觉得我的这篇文章写的不错的话，请给我一个赞与收藏，关注我，我会继续给大家带来更多更优质的干货内容。