My C++ Solution using NFA


  • 0
    B
    class State {
    public:
        State *next;
        bool isTerminal;
        const static char dot = '.';
        const static char star = '*';
        const static char epsilon = '-';
        const static char notoken = ' ';
    
        char token2next;
        char token2myself;
        State(State* _next=nullptr, int _token2next=notoken, int _token2myself=notoken) {
            next = _next;
            token2next = _token2next;
            token2myself = _token2myself;
            isTerminal = false;
        };
    };
    
    class Solution {
    public:
        State* buildNFA(string p) {
            State* start = new State();
            State* cur = start;
            for (int i = 0; i < p.length(); i ++) {
                if (p[i] == State().star) continue;
                cur->next = new State();
                char c = p[i];
                if (p[i+1] == State().star) {
                    cur->token2next = State().epsilon;
                    cur = cur->next;
                    cur->token2myself = c;
                    i += 1;
                }
                else {
                    cur->token2next = c;
                    cur = cur->next;
                    cur->token2myself = State().notoken;
                }
            }
            cur->isTerminal = true;
            return start;
        }
        bool solve(string s, int index, State* state) {
            if (index >= s.length()) {
                if (!state->isTerminal && state->token2next == State().epsilon) {
                    return solve(s, index, state->next);
                }
                else {
                    return state->isTerminal;
                }
            }
            // myself?
            if (state->token2myself == state->dot || state->token2myself == s[index]) {
                if (solve(s, index+1, state)) {
                    return true;
                }
            }
            // next?
            if (state->token2next == state->epsilon) {
                if (solve(s, index, state->next)) {
                    return true;
                }
            }
            else {
                if (state->token2next == state->dot || state->token2next == s[index]) {
                    if (solve(s, index+1, state->next)) {
                        return true;
                    }
                }
            }
            return false;
        }
        bool isMatch(string s, string p) {
            State* start = buildNFA(p);
            return solve(s, 0, start);
        }
    };

Log in to reply
 

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