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

• 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;
}
};``````

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