Classical approach based on NFA, O(N*M + M), 41ms


  • 1
    L

    This is classical implementation for RegularExpression. It's good described in book Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne,and on Coursera.org in Algorithms part 2 course.

    Here some explanation about complexity http://algs4.cs.princeton.edu/54regexp/

    class Solution {
    private:
        void fillDFS(vector<vector<int>> &G, int s, vector<bool> &marked) {
            dfs(G, s, marked);
        }
    
        void fillDFS(vector<vector<int>> &G, vector<int> &sources, vector<bool> &marked) {
            for (int i = 0; i<sources.size(); i++) {
                if (!marked[sources[i]]) dfs(G, sources[i], marked);
            }
        }
    
        void dfs(vector<vector<int>> &G, int v, vector<bool> &marked) { 
            marked[v] = true;
            for (int i = 0; i < G[v].size(); i++) {
                if (!marked[G[v][i]]) dfs(G, G[v][i], marked);
            }
        }
    
    public:
        bool isMatch(const char *s, const char *p) {
            int M = strlen(p);
    
            vector<vector<int>> G;
            for (int i = 0; i<=M; i++) {
                vector<int> t;
                G.push_back(t);
            }
            for (int i = 0; i < M; i++) { 
                // closure operator (uses 1-character lookahead)
                if (i < M-1 && *(p+i+1) == '*') { 
                    G[i].push_back(i+1); 
                    G[i+1].push_back(i); 
                } 
                if (*(p+i) == '*') 
                    G[i].push_back(i+1);
            } 
    
            vector<bool> marked(M+1, 0);
            fillDFS(G, 0, marked);
            unordered_set<int> pc;
            for (int v = 0; v < G.size(); v++)
                if (marked[v]) pc.insert(v);
    
            // Compute possible NFA states for txt[i+1]
            for (int i = 0; i < strlen(s); i++) {
                vector<int> match;
                for (auto it = pc.begin(); it != pc.end(); ++it) {
                    if (*it == M) continue;
                    if ((*(p+*it) == *(s+i)) || *(p+*it) == '.')
                        match.push_back(*it+1); 
                }
                marked.clear();
                marked.resize(M+1, 0);
                fillDFS(G, match, marked);
                pc.clear();
                for (int v = 0; v < G.size(); v++)
                    if (marked[v]) pc.insert(v);
    
                // optimization if no states reachable
                if (pc.size() == 0) return false;
            }
    
            // check for accept state
            for (auto it = pc.begin(); it != pc.end(); ++it)
                if (*it == M) return true;
            return false;
        }
    };

Log in to reply
 

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