[LeetCode] 10. Regular Expression Matching

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

1. DP, code is not elegant enough. Will improve later. Judge the way the code end is an issue, at the boader charAt will not work.

public class Solution {
    
    public int isMatchAux(String s, String p, int indexS, int indexP, int[][] dp){
        int lenS = s.length();
        int lenP = p.length();
        
        if(lenS < indexS || lenP < indexP){
            return -1;
        }
        
        if(0 != dp[indexS][indexP]){
            return dp[indexS][indexP];
        }
        
        if(lenS == indexS && lenP == indexP){
            dp[indexS][indexP] = 1;
            return dp[indexS][indexP];
        }else if(lenS == indexS && indexP < lenP -1 && '*' == p.charAt(indexP + 1)){
            dp[indexS][indexP] = isMatchAux(s, p, indexS, indexP + 2, dp);
            return dp[indexS][indexP];
        }else if(lenS == indexS || lenP == indexP){
            dp[indexS][indexP] = -1;
            return dp[indexS][indexP];
        }
        
        
        char cs = s.charAt(indexS);
        char cp = p.charAt(indexP);
        
        if(0 == dp[indexS][indexP]){
            
            boolean ret = false;
            
            if(indexP < lenP -1 && '*' == p.charAt(indexP + 1) ){
                ret = ret || isMatchAux(s, p, indexS, indexP + 2, dp) == 1;
                if('.' == cp || cs == cp){
                    ret = ret || isMatchAux(s, p, indexS + 1, indexP, dp) == 1;
                    ret = ret || isMatchAux(s, p, indexS + 1, indexP+2, dp) == 1;
                }
            }else if('.' == cp || cs == cp){
                ret = isMatchAux(s, p, indexS + 1, indexP + 1, dp) == 1;
            }
            
            dp[indexS][indexP] = ret ? 1: -1;
        
        }
        
        return dp[indexS][indexP];
    }
    
    public boolean isMatch(String s, String p) {
        int lens = s.length();
        int lenp = p.length();
        
        int[][] dp = new int[lens+1][lenp+1];
        
        return isMatchAux(s, p, 0, 0, dp) == 1? true: false;
    }
}