Simple recursive c++ solution, with comment


  • 0
    G

    Check two string in reverse order due to its " *. " rules.

    class Solution {
    public:
    	bool isMatch(string s, string p) {
    		bool match = false;
    		//check from the tail to the top
    		int i = s.size() - 1, j = p.size() - 1;
    		while (!match) {
    			if (i < 0 && j < 0)
    				return true;
    			else if (j < 0 || (i < 0 && p[j] != '*'))
    				break;
    			if (p[j] == '*') {
    				j--;
    				while (i >= 0 && (s[i] == p[j] || p[j] == '\.')) {
    					//check recursively, when there is a match -- return ture
    					match = match | isMatch(s.substr(0, i + 1), p.substr(0, j));
    					if (match)
    						return true;
    					--i;
    				}
    				j--;
    			}
    			else if (p[j] == '\.' || p[j] == s[i]) {
    				i--;
    				j--;
    			}
    			else
    				break;
    		}
    		return match;
    	}
    };
    

    Recursive solution is always easy isn't it ;). Cost 13ms.


Log in to reply
 

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