C++ NFA solution

• 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
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;
} else {
if(isMatch(state.nfa->c,s[state.sPos]))
{
if(!state.nfa->literal)
{
}
} else {
}
}

}

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

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