宜昌优化网站建设,河南十大建筑公司排名,衡水哪儿专业做网站,做网站销售的换工作题目描述 你有两个字符串#xff0c;即pattern和value。 pattern字符串由字母a和b组成#xff0c;用于描述字符串中的模式。 例如#xff0c;字符串catcatgocatgo匹配模式aabab#xff08;其中cat是a即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
解释 adogdog,b反之也符合规则提示
1 len(pattern) 10000 len(value) 1000你可以假设pattern只包含字母a和bvalue仅包含小写字母。
解题思路与代码暴力破解 剪枝 这道题的核心其实就只有一个问题。就是如何去用ab匹配到对应的单词匹配到返回true匹配不到返回false。 那么如何匹配呢首先我们要去搞清楚一个问题那就是a有多少个b有多少个。这么做的目的是确定ab在对应的字符串中匹配的范围为的其实就是在最后匹配的环节中不要去做无用的匹配。这里我们还有去做一步优化那就是要使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) {// 创建两个变量ab并且使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’ 可以对应空字符串这增加了问题的复杂性。处理这类问题需要考察者对边界情况的敏感度和处理能力。
综上这道题目的意义主要在于考察程序员的实际编程能力、对算法复杂度的理解以及对边界情况的处理能力。
最后的最后如果你觉得我的这篇文章写的不错的话请给我一个赞与收藏关注我我会继续给大家带来更多更优质的干货内容。
