我人傻了,这题着实恶心到我了,特在此记录一下。
leetcode 每日一题,面试题 16.18. 模式匹配 。
只给自己看,代码实现太烂,记录一下需要注意的细节:
1. 首先是边界,如果p和v同时为空时,为true,当p为空时,一定不能匹配,当v为空时,可能会被单a或者单b匹配到;
2. 第二个就是全a或者全b实现情况;
3. 第三个是遍历la时,lb算出来的结果可能为负,肯定是不合常理的,长度不能为负。
class Solution {
public:
bool patternMatching(string p, string v) {
if(p.empty() && v.empty()) return true;
if(p.empty()) return false;
int ca = count(p.begin(), p.end(), 'a'), cb = p.size() - ca;
int lp = p.size(), lv = v.size();
// 全为a或者全为b时。
if(!ca || !cb) {
if(lv % lp) return false;
else{
int l = lv / lp;
int t = 0;
string s = v.substr(0, l);
while(lp --){
if(s != v.substr(t, l)) return false;
t += l;
}
return true;
}
}
// la 长度从0到lv长度
for(int i = 0; i <= lv; ++ i){
if((lv - i * ca) % cb == 0){
int lb = (lv - i * ca) / cb;
int la = i;
if(lb < 0) break;
//cout << lb << " " << la << endl;
string sa, sb;
// 判别是否是第一次
bool fa = true, fb = true;
int t = 0;
for(int j = 0; j < lp; ++ j){
if(p[j] == 'a'){
if(fa){
sa = v.substr(t, la);
fa = false;
//cout << sa << endl;
}
else {
if(sa != v.substr(t, la)) break;
//cout << sa << endl;
}
t += la;
}else{
if(fb){
sb = v.substr(t, lb);
fb = false;
//cout << sb << endl;
}
else{
if(sb != v.substr(t, lb)) break;
//cout << sb << endl;
}
t += lb;
}
}
if(t == lv){
//cout << la << " " << lb << endl;
return sa != sb;
}
}
}
return false;
}
};