Problem Description

Given an input string (s) and a pattern (p), 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).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.

Java:

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

// accepted DP solution
class Solution {
    public boolean isMatch(String s, String p) {
        int[][] dp = new int[s.length()+1][p.length()+1];
        return helper(s.toCharArray(), 0, p.toCharArray(), 0, dp);
    }
    
    private boolean helper(char[] s, int si, char[] p, int pi, int[][] dp) {
        if (si == s.length && pi == p.length) return true;
        if (dp[si][pi] == 1) return false;
        
        if (si == s.length) {
            if ((p.length - pi) % 2 != 0) {
                dp[si][pi] = 1;
                return false;
            } else {
                if (p[pi+1] == '*' && helper(s, si, p, pi+2, dp)) {
                    return true;
                } 
                dp[si][pi] = 1;
                return false;
            }
        } else if (pi == p.length) {
            dp[si][pi] = 1;
            return false;
        }
        
        if (s[si] == p[pi] || p[pi] == '.') {
            if (pi + 1 != p.length && p[pi+1] == '*' && 
                (helper(s, si+1, p, pi, dp) || helper(s, si+1, p, pi+2, dp) || helper(s, si, p, pi+2, dp)) 
               || helper(s, si+1, p, pi+1, dp)) {
                return true;
            }
        } else {
            if (pi + 1 != p.length && p[pi+1] == '*' && helper(s, si, p, pi+2, dp)) {
                return true;
            }
        }
        dp[si][pi] = 1;
        return false;
    }
}