My 8ms C++ Solution with comments


  • -1
    W
    /*
    	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;
    	}
    };

  • 0
    M

    For the case:
    s = aaaabbac
    p = ab*ac.
    The expected answer is false.


  • 0
    W

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


Log in to reply
 

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