Detailed explanation of the recursive algorithm with Java code


  • 0
    L

    We have plenty of Java code examples in this discussion. It took me a while to get it right but I managed to understand this algo after going through the discussion forum. Thanks to everyone for sharing their solution but my solution is based on https://discuss.leetcode.com/topic/41924/simple-java-recursive-solution-with-two-cases because this is closest to my style. Let us look at the examples to build up our algo:

    isMatch("aa","a") ? false
    isMatch("aa","aa") ? true
    isMatch("aaa","aa") ? false
    isMatch("aa", "a*") ? true
    isMatch("aa", ".*") ? true
    isMatch("ab", ".*") ? true
    isMatch("aab", "c*a*b") ? true
    

    Things to consider while writing an algorithm:

    1. Position-by-position match between s and p should be done between matching characters, or when p contains a '.'.
    2. The above may immediately return false in case things don't match as expected.
    3. However, the rule-breaker of the above is when the next character may contain a ''. Why? ..look at a few examples:
      "aa" and "a
      " will work with character matching
      "aa" and ".*" may work with the character matching

    but it fails with: "aaab" and "cab"

    The idea is that the character before * may or may not match but it may still be a valid regex and that could only be decided when we go till the end of the string. We are left with two choices for this part:

    a. We will see if our characters at i and j match, if they do, we should call the function recursively on the rest of the string with the same pattern assuming that there may be more further matches. It is essentially saying:

      if(isMatch(s,i+1,p,j)) {
         return true;
      }
    

    We will backtrack if it doesn't work. An example where it works is "a*" and "aa".

    b. If the first didn't work, we know that the characters didn't match (ex. "aaab" and "cab"), we will ignore the current character in the pattern since it may not be present and try with the same s with the next set of pattern that will be past the current '*'.

    if(isMatch(s,i,p,j+2)) {
       return true;
     }
    

    So from our example of "aaab" and "cab", after comparing "a" and "c" , it will now move to comparing "a" and "a*b".

    Hope it helps someone.

        private boolean helper(String s, int i, String p, int j) {
            if(j==p.length()) {
                return s.length()==i;
            }
            
            if(j+1<p.length() && p.charAt(j+1)=='*') {
                if (i<s.length() && (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i))){
                    if(helper(s, i + 1, p, j)) {
                        return true;
                    }
                }             
                if (helper(s, i, p, j + 2)) {
                    return true;
                }           
                return false;
            }        
            if(i<s.length() && (p.charAt(j)=='.' || p.charAt(j)==s.charAt(i))) {         
                return helper(s,i+1,p,j+1);
            }                    
            return false;
        }
    

Log in to reply
 

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