侯门一入深如海
从此萧郎是路人
字符串匹配题。。。
题目如果简化一下，已知a对应的字符串的长度len_a以及数量cnt_a，b对应的字符串的长度len_b以及数量cnt_b，这样是不是就能很快求解出a对应的字符串是什么以及b对应的字符串是什么，然后再判断是否match。。。
因为cnt_a以及cnt_b在pattern中可以得到，所以问题就变成了，如果求解a对应的字符串的长度len_a以及b对应的字符串的长度len_a。。。
答案就是枚举！枚举len_a在[0, len_value]之间的所有值。。。就能求解出所有对应的len_b，然后逐一计算是否match。。。
求解len_b就是一个公式：
其中所有数都是整数，N表示value的长度。
当然这道题更麻烦的在于各种各样的边界测试用例。。。
而且要区分字符串不存在以及字符串为空串。。。
class Solution {
private:
bool match(string &&pattern, string &&value, string &&a, string &&b) {
string new_val = "";
for (const char &it : pattern) {
if (it == 'a')
new_val += a;
else new_val += b;
}
return new_val == value;
}
public:
bool patternMatching(string pattern, string value) {
int n = value.length();
int cnt_a = 0;
int cnt_b = 0;
for (const char &it : pattern) {
if (it == 'a') cnt_a++;
else cnt_b++;
}
if (pattern.empty() && n == 0) return true;
else if (pattern.empty() && n > 0) return false;
if ((cnt_a == 0 || cnt_b == 0) && n == 0)
return true;
if (cnt_a == 1 && cnt_b != 1) {
string a = value;
string b = "";
if (match(std::move(pattern), std::move(value), std::move(a), std::move(b)))
return true;
}
if (cnt_b == 1 && cnt_a != 1) {
string b = value;
string a = "";
if (match(std::move(pattern), std::move(value), std::move(a), std::move(b)))
return true;
}
for (int len_a = 0; len_a * cnt_a <= n && len_a < n; len_a++) {
if (cnt_b == 0 || (n - cnt_a * len_a) % cnt_b == 0) {
int len_b = 0;
if (cnt_b != 0) len_b = (n - cnt_a * len_a) / cnt_b;
if (pattern[0] == 'a') {
string a = value.substr(0, len_a);
string b = "";
size_t b_pos = pattern.find('b');
if (b_pos != std::string::npos)
b = value.substr(b_pos * len_a, len_b);
if (a != b && match(std::move(pattern), std::move(value), std::move(a), std::move(b)))
return true;
} else {
string b = value.substr(0, len_b);
string a = "";
size_t a_pos = pattern.find('a');
if (a_pos != std::string::npos)
a = value.substr(a_pos * len_b, len_a);
if (match(std::move(pattern), std::move(value), std::move(a), std::move(b)))
return true;
}
}
}
return false;
}
};
