# My 8ms C++ Solution with comments

• ``````/*
https://leetcode.com/problems/regular-expression-matching/
Description:
for each character in p, we scan the match list for it.
e.g.
s = aaaabbac
p = ab*ac
(index is 0-based)
We always compare the next character in s to the index in the match list. the initial match list is {-1}
the first character 'a', we have {0,1,2,3,6} as the 'a''s match list.
then we scan b*, from the index exist in the last match list, but here we need the copy the last match list to the current match
list first, because b* can be a null string.
then we get { 0('a'),1('a'),2('a'),3('a'),4('b'),5('b'),6('a') } as b's match list
then we scan the next character 'a''s match list, from the index that exist in the last match list, b's.
we get { 1,2,3,6 }
here we come to the last character 'c'.
we only find { 7 }, because 6 is 'a' and 7 is 'c'.
we trace the maximumId that we've reached, that is, 7, and now we've finished the p string.
7 means we've finished the s string as well. So, Accept.
If both pattern and s string are null, we Accept.

The condition that we Reject:
if a character doesn't match anything, its match list is null. we Reject.
if we go through the whole p string, and the maximumId we can reach doesn't cover the whole s string, that means
this pattern only matchs part of s string, we Reject.

2015-09-13
*/
class Solution {
public:
bool equal(char ch1, char ch2) {
if (ch1 == '.' || ch2 == '.') return true;
else return ch1 == ch2;
}
bool isMatch(string s, string p) {
int i=0;
int j = 0;
int maxIndex=-1;
if (s.empty() && p.empty()) return true;
set<int> lastMatchList;
lastMatchList.insert(-1);
do {
set<int> curMatchList;
if (p[j + 1] == '*') {
curMatchList = lastMatchList;		// when a* equals to e, the its OKlist is same with the lastOKlist
for (auto i : curMatchList) {
if (s[i+1] && equal(s[i+1], p[j])) {
curMatchList.insert(i+1);
maxIndex = max(i + 1, maxIndex);
}
}
j+=2;
} else {
maxIndex = -1;
for (auto i : lastMatchList) {
if (s[i + 1] && equal(s[i + 1], p[j])) {
curMatchList.insert(i + 1);
maxIndex = max(i + 1, maxIndex);
}
}
j++;
}
swap(curMatchList, lastMatchList);
} while (p[j] && !lastMatchList.empty());
if (!lastMatchList.empty() && maxIndex == s.size() - 1)
return true;
return false;
}
};``````

• For the case：
s = aaaabbac
p = ab*ac.

• Yes, the program did output false. Plz check your test case again.

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