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

public boolean isMatch(String s, String p) {
    int sLen = s.length(), pLen = p.length();
    boolean[][] dp = new boolean[sLen + 1][pLen + 1];
    dp[0][0] = true;

    // Judges if p can match empty string.
    for(int i = 1; i <= pLen; i++) {
        if(p.charAt(i - 1) == '*') {
            dp[0][i] = dp[0][i - 2];
        }
    }

    for(int i = 1; i <= sLen; i++) {
        for(int j = 1; j <= pLen; j++) {
            if(s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
                dp[i][j] = dp[i - 1][j - 1];
            } else if(p.charAt(j - 1) == '*') {
                if(s.charAt(i - 1) != p.charAt(j - 2) && p.charAt(j - 2) != '.') {
                    dp[i][j] = dp[i][j - 2];
                }else {
                    // match empty || match many
                    dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                }
            }
        }
    }
    return dp[sLen][pLen];
}

results matching ""

    No results matching ""