Ac solution code


  • 0

    The basic idea is similar as merge sort, just check the left-most char each time, if doesn't match, then backtrack from posOfStar + 1.

    public boolean isMatch(String str, String pattern) {
    	return isMatch(str, 0, pattern, 0);
    }
      
    public boolean isMatch(String str, int si, String pattern, int pi) {
    	if (pi > pattern.length() - 1)
    		return si > str.length() - 1; 
    	
    	if (pi + 1 < pattern.length() && pattern.charAt(pi + 1) == '*') {
    		while (si < str.length() && (pattern.charAt(pi) == '.' || pattern.charAt(pi) == str.charAt(si))) {
    			if (isMatch(str, si, pattern, pi + 2))
    				return true;
    			si++;// Backtrack
    		}
    		return isMatch(str, si, pattern, pi + 2);// No * is matched.
    	} else // Next char is not *
    		return (si < str.length() && (pattern.charAt(pi) == str.charAt(si) || pattern.charAt(pi) == '.')) && isMatch(str, si+1, pattern, pi + 1);    			
    }

Log in to reply
 

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