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

Referrence Source

Referrence Source 2: using a 2D DP

Here are some conditions to figure out, then the logic can be very straightforward.

1, If p.charAt(j) == s.charAt(i) :  dp[i][j] = dp[i-1][j-1];
2, If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
3, If p.charAt(j) == '*': 
   here are two sub conditions:
1   if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2]  //in this case, a* only counts as empty
2   if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':
        dp[i][j] = dp[i-1][j]    //in this case, a* counts as multiple a 
        or dp[i][j] = dp[i][j-1]   // in this case, a* counts as single a
        or dp[i][j] = dp[i][j-2]   // in this case, a* counts as empty

For problems like regular expression matching, the first thing to consider is to build a DP array.

class Solution {
   public boolean isMatch(String s, String p) {
       if (p.isEmpty()) {
            return s.isEmpty();
        }
        if (p.length() > 1) {
            if (p.charAt(1) == '*') {
                return isMatch(s, p.substring(2)) || 
                    !s.isEmpty() && (s.charAt(0) == p.charAt(0) || 
                    p.charAt(0) == '.') && isMatch(s.substring(1), p);
            } else {
                return !s.isEmpty() && (s.charAt(0) == p.charAt(0) || 
                p.charAt(0) == '.') && isMatch(s.substring(1), p.substring(1));
            }
        } else {
            return !s.isEmpty() && (s.charAt(0) == p.charAt(0) || 
            p.charAt(0) == '.') && isMatch(s.substring(1), p.substring(1));
        }
   }
}