题解 | #正则表达式匹配#

自动机解法，需要保持Pattern的最简性，不然会超时。

#include <string>
#include <unordered_map>
#include <vector>
struct Node{
    char ch;
    bool star;
    Node* next;
    // vector<Node*> children;
    Node(char c){
        ch = c;
        star = false;
    };
};
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    
    Node* buildGraph(string pattern){
        Node* start = new Node('S');
        Node* head = start;
        Node* prev = start;
        for(int i=0;i<pattern.size();i++){
            if((pattern[i]>='a'&&pattern[i]<='z')||(pattern[i]=='.')){
                Node* next = new Node(pattern[i]);
                prev = head;
                head->next = next;
                head = head->next;
            }
            else if(pattern[i]=='*'){
                if(head->ch==prev->ch&&prev->star){
                    prev->next = nullptr;
                    head = prev;
                    continue;
                }
                else head->star = true;
            }
        }
        Node* end = new Node('E');
        head->next = end;
        return start->next;
    }

    bool matchGraph(string str, Node* pattern){
        if((str.length()==0&&pattern->ch=='E')||(str.length()==0&&pattern->next->ch=='E'&&pattern->star)) return true;
        else if(str.length()==0) return false;
        else if(pattern->ch=='E') return false;
        if(pattern->ch=='.'){
            if(pattern->star){
                return (matchGraph(string(str.begin()+1, str.end()), pattern)||matchGraph(string(str.begin()+1, str.end()), pattern->next)||(matchGraph(string(str.begin(), str.end()), pattern->next)));
            }
            else{
                return matchGraph(string(str.begin()+1, str.end()), pattern->next);
            }
        }
        else if(pattern->ch>='a' && pattern->ch<='z'&&str[0]==pattern->ch){
            if(pattern->star){
                return (matchGraph(string(str.begin()+1, str.end()), pattern)||matchGraph(string(str.begin()+1, str.end()), pattern->next)||(matchGraph(string(str.begin(), str.end()), pattern->next)));
            }
            else{
                return matchGraph(string(str.begin()+1, str.end()), pattern->next);
            }
        }
        else if(pattern->ch>='a' && pattern->ch<='z'&&str[0]!=pattern->ch&&pattern->star){
            return matchGraph(string(str.begin(), str.end()), pattern->next);
        }
        else{
            return false;
        }
    }

    bool match(string str, string pattern) {
        // write code here
        auto patternGraph  = buildGraph(pattern);
        // patternGraph = patternGraph->next;
        return matchGraph(str, patternGraph);
    }
};