Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character. '*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be: bool isMatch(const char s, const char p)

Some examples:
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

Solution

public class Solution {
    public boolean isMatch(String s, String p) {
        if(s == null && p == null) return true;
        if(s == null || p == null) return false;

        return dfs(s, 0, p, 0);
    }

    public boolean dfs(String s, int sIdx, String p, int pIdx) {
        if(s.length() == sIdx && p.length() == pIdx) return true;
        if(s.length() != sIdx && p.length() == pIdx) return false; // p empty, s still has, must be false

        if(pIdx + 1 < p.length() && p.charAt(pIdx + 1) == '*') {
            if(dfs(s, sIdx, p, pIdx + 2)) return true; // it can be ignored
            for(int i = sIdx; i < s.length(); i++) {
                if(s.charAt(i) == p.charAt(pIdx) || p.charAt(pIdx) == '.') {
                    if(dfs(s, i + 1, p, pIdx + 2)) return true;
                } else {
                    break;
                }
            }
        } else {
            // something you must match
            if(sIdx < s.length() && ( s.charAt(sIdx) == p.charAt(pIdx) || p.charAt(pIdx) == '.') ) {
                if(dfs(s,sIdx+1,p,pIdx+1)) return true;
            } else {
                return false;
            }
        }

        return false;
    }
}