Verbose case by case recursion solution C++ 6ms


  • 0
    B
    class Solution
    {
    public:
    	bool isMatch(string a, string b){
    		return rec(a, a.size() - 1, b, b.size() - 1);   
                    // scan from right to left, since '*' only process leftward chars
    	}
    
    	bool rec(string& a, int ia, string& b, int ib){
    		if (ia == -1 && ib == -1)
    			return true;
    		if (ia == -1){
    			if (b[ib] == '*'){
    				return rec(a, ia, b, ib - 2);  // for cases :   [], [c*c*]
    			}
    			return false;
    		}
    		if (ib == -1)
    			return rec(b, ib, a, ia);
    
    
    		if (a[ia] != '*' && b[ib] != '*')
    			return (a[ia] == '.' || b[ib] == '.' || a[ia] == b[ib]) && rec(a, ia - 1, b, ib - 1);
    
    
    		if (a[ia] == '*' && b[ib] == '*'){
    			if (a[ia - 1] == b[ib - 1])
    				return rec(a, ia - 2, b, ib - 2);
    			else
    				return rec(a, ia, b, ib - 2) || rec(a, ia - 2, b, ib);
    		}
    
    
    		if (a[ia] == '*')
    			return rec(b, ib, a, ia);
    
    		//if (b[ib] == '*'){
    		char rep = b[ib - 1];
    
    		if (rep != '.'){
    			bool tmp = false;
    			for (; ia >= -1 && a[ia] == rep; --ia){  // for case: [aaa], [a*b*a*], you cannot simply skip all 'a', you have to check position one by one. 
    				tmp |= rec(a, ia, b, ib - 2);
    				if (tmp)
    					return true;
    			}
    			return rec(a, ia, b, ib - 2);
    		}
    		else{
    			bool tmp = false;
    			for (; ia >= -1; --ia){		// for case: [aaa], [.*]. Here [.*] means [....] which can mean any equivalently long strings. 
    				tmp |= rec(a, ia, b, ib - 2);
    				if (tmp)
    					return true;
    			}
    			return false;
    		}
    	//	}
    	}
    };
    

Log in to reply
 

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