Regular Expression Matching DFS.java

public class Solution {
    
    public boolean isMatch(String s, String p) {
        return dfs(s, p, 0, 0);
    }
    
    private boolean dfs(String s, String p, int i, int j) {
        
        //if we arrive at the end of p, but we have not arrived at the end of s,
        //they will not match since it is impossible to  match the rest part of s
        //On the other hand, if we arrive at the end of s, but we have not arrive
        //the end of p, it still may match, if next is [a-z]*, if not they are
        //still not match. So when we arrive at the end of s, we must judge it
        //to be false, when next char of p is not *. Namely, when we arrive at the
        //end of s, we will still keep the program on going
        if (j == p.length())
            return i == s.length();

            
        //when j + 1 is not '*'
        //j cannot be * since we will skip '*'
        //when j is at last, the next cannot be '*'
        if (j == p.length() - 1 || p.charAt(j + 1) != '*') {
            if ( i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.'))
                return dfs(s,p, i + 1, j + 1);
            else // if we arrive at the end of s and we find they are not match, namely the next of p is not * and i doesn't match j
                return false;
        }
        
        //when  j + 1 is '*'
        while (i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.')) {
            //if one match, then it match. Using or is not convenient, use if
            if (dfs(s, p, i, j + 2))
                return true;
            i++;//i match, i + 1 match, i + 2 match....
        }
        
        //we should also dfs the one which doest't match the jth character in p or i
        //reaches s end, for example, "aab", "c*a*b" and "aa", "a*b*"
        //if we still not arrive at the end of p, but we have arrived at the end  of s,
        //we keep going and find if the the next one can still matching, until we arrive
        //at the end of p, or we find that they are not match
        return dfs(s, p, i, j + 2);
    }
}