leetcode-面试题 16.18-模式匹配
class Solution {
public:
bool patternMatching(string pattern, string value) {
vector<int> cnt = pre(pattern);
if (pattern == "") return value == "";
if (value == "") return pattern == "" || (cnt[0] == 1 && cnt[1] == 0);
if (cnt[1] == 0) {
int l;
if ((value.length() % cnt[0]) != 0) return false;
else l = value.length() / cnt[0];
string s = value.substr(0, l);
for (int k = l ; k < value.length(); k+=l) {
if (value.substr(k, l) != s) return false;
}
return true;
}
for (int i = 0; i <= value.length() / cnt[0]; ++i) {
mp = {"", ""};
int flag = 0; //匹配到哪一位
int la = i, lb;
if ((value.length() - (la * cnt[0])) % cnt[1] != 0) continue;
else lb = (value.length() - (la * cnt[0])) / cnt[1];
for (int j = 0; j <= pattern.length(); ++j) {
if (j == pattern.length()) return true;
if (flag >= value.length()) break;
if (pattern[j] == 'a') {
if (mp[0].length() == 0) {
mp[0] = value.substr(flag, la);
if (mp[0] == mp[1] && la != 0) break;
flag = flag + la;
}
else {
if (mp[0] != value.substr(flag, la)) break;
flag = flag + la;
}
}
if (pattern[j] == 'b') {
if (mp[1].length() == 0) {
mp[1] = value.substr(flag, lb);
if (mp[0] == mp[1] && lb!=0) break;
flag = flag + lb;
}
else {
if (mp[1] != value.substr(flag, lb)) break;
flag = flag + lb;
}
}
}
}
return false;
}
private:
vector<string> mp; //0a1b;
vector<int> pre(string &pattern) {
vector<int> res = {0,0}; //A[0] B[1]
for (auto s : pattern) {
if (s == 'a') res[0]++;
else res[1]++;
}
if (res[0] < res[1]) {
swap(res[0], res[1]);
for (auto &s : pattern) {
if (s == 'a') s = 'b';
else s = 'a';
}
}
return res;
}
};