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());
    }
};

LeetCode-10 Regular Expression Matching