Description
给定文本串\(s\)和模式串\(p\)，实现带有'.'和'*'功能的正则表达式，其中：
'.'匹配任一字符。'*'匹配零个或多个的前一字符。
Constraints
- \(1 \le \ \mid s \mid \ \le 20\)
- \(1 \le \ \mid p \mid \ \le 20\)
Solution
一眼D……不DP了，换个口味吧，试试有穷自动机。基本思路就是不同的状态区分接收不同的字符。本题目中的状态不会指向'*'，这并非错误，只是会制造多余的状态。其他细节看注释。
时间复杂度证明：设模式串的长度为\(n\)，文本串的长度为\(m\)。由于自动机最多拥有\(O(n)\)个状态，而且在迭代次数为\(O(m)\)次的扫描文本串过程中，状态转移只会花费\(O(1)\)成本以保留原地或者向前直到指向结束符，因此时间复杂度是\(O(nm)\)。
Code
class Solution {
public:
bool isMatch(const std::string& s, const std::string& p) {
using FA = unordered_set<int>;
FA states {0};
auto update_char = [&](char c) {
FA new_states;
for(auto state : states) {
// 已经处于终止状态
if(state == p.size()) continue;
// 无法匹配
if(p[state] != c && p[state] != '.') continue;
// 允许零次/多次匹配
// 由于update_self()是包含指向结束符的，如果只走当前的if，也能在后续update_self正确转移到结束符
// 因此下面的普通匹配可以用else区分，而不是每次都再加上state + 1状态
if(state + 1 < p.size() && p[state + 1] == '*') {
new_states.emplace(state);
// 一次普通的匹配'.'或者c，但是这里不需要将状态指向'*'，所以用else判断（上面解释原因了）
} else {
new_states.emplace(state + 1);
}
}
states.swap(new_states);
};
auto update_self = [&] {
FA new_states;
for(auto state : states) {
// 找到连续的'*'后继的状态，直到指向结束符（含）
// Example 1: a*b*cd.*e*\0; Example 2: a*b*cd.*e*\0
// ^ ^ ^ ^ ^ ^
// 示例1中初始时状态为0指向'a'，update后可以新增状态2和4
// 示例2中只有一个状态6指向'.'，update后可以新增状态8和10（指向结束符）
while(state + 1 < p.size() && p[state + 1] == '*') {
auto [_, nobody] = new_states.emplace(state += 2);
// 避免重复计算引起时间复杂度上升
if(!nobody) break;
}
}
states.merge(new_states);
};
for(update_self(); auto c : s) {
update_char(c);
update_self();
}
return states.contains(p.size());
}
};