[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;
    }
}

[LeetCode] 5. Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

1. DP, O(N^2) complexity.

https://github.com/csehao/LeetCode/blob/master/Java/LongestPalindrome.java

public class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        
        StringBuilder sb = new StringBuilder();
        if(0 == len)
            return sb.toString();
            
        boolean[][] dp = new boolean[1001][1001];
        
        int l = 0;
        int u = 1;
        
        for(int i = 0; i < len; ++i){
            dp[i][i+1] = true;
        }
        
        for(int i = 0; i < len-1; ++i){
            if(s.charAt(i) == s.charAt(i+1)){
                dp[i][i+2] = true;
                l = i;
                u = i+2;
                
            }
            else{
                dp[i][i+2] = false;
            }
        }

        for(int d = 3; d <= len; ++d){
            for(int i = 0; i<=len-d; ++i){
                if(s.charAt(i) == s.charAt(i+d-1)){
                    dp[i][i+d] = dp[i+1][i+d-1];
                    if(dp[i][i+d] == true){
                        l = i;
                        u = i+d;
                    }
                }
                else{
                    dp[i][i+d] = false;
                }
            }
        }
        
        return s.substring(l, u);
        
    }
}