C++ NFA solution


  • 0
    J

    I don't know why but I really wanted to do an NFA solution. I took a look at and adapted it to the needs of this problem https://swtch.com/~rsc/regexp/regexp1.html

    Basically you convert the regex string to a list of NFAs and then run through each possible state.

    I don't think it's possible to do a DFA with the non-greedy operator, but I would love to someone come up with a solution for one.

    class Solution {
            public:
                    bool isMatch(string s, string p) {
                            NFA* nfaList = buildNFAs(p); //convert regex to list of NFAs
                           
                            queue<State> sList; //list of upcoming states
                            addState(&sList,0,nfaList); //create first state and add it to the state list.
                            State state; //current state
    
                            while(!sList.empty())
                            {
                                    cout << "============================" << endl;
    
                                    state = sList.front();
                                    sList.pop();
    
                                    printState(&state);
    
                                    if(state.nfa->c == '\0' || state.sPos == s.size()) //check if this state contains last possible NFA or is at the end of the string
                                    {
                                            if(state.sPos == s.size() && state.nfa->c == s[state.sPos]) //if you are at at last possible NFA and you are at the end of the string, match!
                                                    return true;
                                            addState(&sList,state.sPos,state.nfa->nomatch);
                                    } else {
                                            if(isMatch(state.nfa->c,s[state.sPos]))
                                            {
                                                    addState(&sList,state.sPos+1,state.nfa->match);
                                                    if(!state.nfa->literal)
                                                    {
                                                            addState(&sList,state.sPos+1,state.nfa->nomatch);
                                                            addState(&sList,state.sPos,state.nfa->nomatch);
                                                    }
                                            } else {
                                                    addState(&sList,state.sPos,state.nfa->nomatch);
                                            }
                                    }
    
                            }
    
                            return false;
                    }
    
            private:
                    struct NFA {
                            char c;
                            bool literal;
                            NFA* match;
                            NFA* nomatch;
                            unordered_map<int,bool> tested;
                    };
                    struct State {
                            int sPos;
                            NFA *nfa;
                    };
                    void addState(queue<State>* sList, int sPos, NFA* nfa)
                    {
                            if(nfa == NULL || nfa->tested[sPos])
                                    return;
                            nfa->tested[sPos] = true;
                            State t;
                            t.sPos = sPos;
                            t.nfa = nfa;
                            sList->push(t);
                    }
                    void printState(State * state)
                    {
                            cout << "S Pos: " << state->sPos;
                            cout << " NFA: " << state->nfa;
                            cout << endl;
                    }
                    void printNFA(NFA * nfa)
                    {
                            cout << "NFA: " << nfa;
                            cout << " char: " << nfa->c;
                            cout << " literal: " << (nfa->literal ? "true" : "false");
                           cout << " match: " << nfa->match;
                           cout << " nomatch: " << nfa->nomatch;
                           cout << endl;
                    }
                    bool isMatch(char a, char b)
                    {
                            return a == b || a == '.';
                    }
    
    
                    NFA* buildNFAs(string expression){
                            NFA* curNFA = new NFA;
                            NFA* retNFA = curNFA;
                            for(int i = 0; i < expression.size(); i++)
                            {
                                    if(expression[i] != '*')
                                    {
                                            curNFA->c = expression[i];
                                            curNFA->match = new NFA;
                                            curNFA->nomatch = NULL;
                                            curNFA->literal = expression[i+1] == '*' ? false : true;
                                            curNFA = curNFA->match;
                                    }
                            }
    
                            curNFA->c = '\0';
                            curNFA->match = NULL;
                            curNFA->nomatch = NULL;
    
                            curNFA = retNFA;
    
                            while(curNFA->c != '\0')
                            {
                                    if(curNFA->literal == false)
                                    {
                                            curNFA->nomatch = curNFA->match;
                                            curNFA->match = curNFA;
                                            printNFA(curNFA);
                                            curNFA = curNFA->nomatch;
                                    } else {
                                            printNFA(curNFA);
                                            curNFA = curNFA->match;
                                    }
    
                            }
    
                            return retNFA;
                    }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.