LeetCode 面试题 16.18. 模式匹配

题目：

你有两个字符串，即pattern和value。 pattern字符串由字母"a"和"b"组成，用于描述字符串中的模式。例如，字符串"catcatgocatgo"匹配模式"aabab"（其中"cat"是"a"，"go"是"b"），该字符串也匹配像"a"、"ab"和"b"这样的模式。但需注意"a"和"b"不能同时表示相同的字符串。编写一个方法判断value字符串是否匹配pattern字符串。

1 <= len(pattern) <= 1000
0 <= len(value) <= 1000
pattern只包含字母"a"和"b"，value仅包含小写字母。

解法：

由于pattern和value都不长，所以可以枚举lenA(lenB可以直接算出来)来验证。验证时可以使用字符串的哈希匹配来做。注意，本题的边界情况比较麻烦，需要写几个特判的情况。

结果：

代码：

 1 class Solution {
 2 public:
 3     bool patternMatching(string pattern, string value) {
 4         initHash(value);
 5         int numA = 0, numB = 0;
 6         for (char c : pattern)
 7             c == 'a' ? numA++ : numB++;
 8         if (value.length() == 0) //value为空串，pattern中a和b只能出现一种
 9             return !numA || !numB;
10         for (int lenA = 1; lenA <= value.length(); lenA++) {
11             int lenB = 0;
12             if (numA * lenA > value.length())
13                 break;
14             if (!numB) {
15                 if (value.length() % lenA) {
16                     continue;
17                 }
18             }
19             else if ((value.length() - numA * lenA) % numB) {
20                 continue;
21             }
22             else {
23                 lenB = (value.length() - numA * lenA) / numB;
24             }
25             if (check(pattern, value, lenA, lenB))
26                 return true;
27         }
28         return false;
29     }
30 private:
31     ll hash[1020]; //hash[i]表示value[0,i)的哈希值
32     ll exp[1020]; //exp[i] == base^i
33     ll base = 29, mod = 1e9 + 7;
34     void initHash(string& value) {
35         exp[0] = 1;
36         for (int i = 1; i < 1020; i++) {
37             exp[i] = (exp[i - 1] * base) % mod;
38         }
39         hash[0] = 0;
40         for (int i = 1; i <= value.length(); i++) {
41             hash[i] = (hash[i - 1] * base + value[i - 1] - 'a') % mod;
42         }
43     }
44     ll compHash(string& value, int l, int r) {//计算value[l,r)的哈希 比如[1,2) 
45         return (hash[r] - (hash[l] * exp[r - l]) % mod + mod) % mod;
46     }
47     bool check(string& pattern, string& value, int lenA, int lenB) {
48         int cur = 0;
49         ll valA = -1LL, valB = -1LL;
50         for (char p : pattern) {
51             ll* pval;
52             int len;
53             if (p == 'a') {
54                 pval = &valA;
55                 len = lenA;
56             }
57             else {
58                 pval = &valB;
59                 len = lenB;
60             }
61             ll ha = compHash(value, cur, cur + len);
62             if (*pval < 0)
63                 *pval = ha;
64             else {
65                 if (*pval != ha)
66                     return false;
67             }
68             cur += len;
69         }
70         return valA != valB;
71     }
72 };