[Leetcode] 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

正则表达式匹配，比较复杂的题目，可以用递归也可以用DP写，这次用递归写的，但是仍然有许多小错误，匹配的过程大概是：

1. 当两个串都是空串的时候，那么返回为true，否则一个空一个不空那么返回false
2. 当模式串的第二个字符不是‘*’的时候，比较当前字符，如果字符相等或者模式串是“.”的话，那么继续匹配子串
3. 如果是‘*’的话，那么要穷举所有目标串中从头开始能与‘*’匹配的项目，然后看剩余子串是否能够匹配

    public boolean isMatch(String s, String p) {
        if(p.length() == 0 && s.length() == 0) return true;
        else if(p.length() == 0 && s.length() != 0) return false;
        
        if(p.length() >= 2 && p.charAt(1) != '*') {
            return s.length() > 0 && (s.charAt(0) == p.charAt(0) | p.charAt(0) == '.') && isMatch(s.substring(1), p.substring(1));
        }
        else if(p.length() >= 2 && p.charAt(1) == '*'){
            int i = 1; // start from 1 so that at least match one character in order to avoid infinite recurse
            while(i <= s.length() && (s.charAt(i-1) == p.charAt(0) | p.charAt(0) == '.')) {
                if(isMatch(s.substring(i), p.substring(2))) return true;
                i++;
            }
            return isMatch(s, p.substring(2)); // with out matching any character
        }
        
        return s.length() > 0 && (s.charAt(0) == p.charAt(0) | p.charAt(0) == '.') && isMatch(s.substring(1), p.substring(1));
    }

The dp version of the solution is as follow, the main part is the same with Wildcard Matching, the difference is how we update dp[i][j] when we find a '*', since '*' could only match multi times of the character in front of it, so dp[i][j-2] stands for match nothing, dp[i][j-1] stands for match one times, dp[i-1][j-1] match two times and dp[i-1][j] match more than two times.

    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        for(int i = 0; i <= m; i++) {
            for(int j = 0; j <= n; j++) {
                if(i == 0 && j == 0)
                    dp[i][j] = true;
                else if(i != 0 && j == 0)
                    dp[i][j] = false;
                else if(i == 0 && j != 0) {
                    if(j > 1 && p.charAt(j-1) == '*')
                        dp[i][j] = dp[i][j-2];
                    else
                        dp[i][j] = false;
                }
                else {
                    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(j > 1 && (p.charAt(j-2) == s.charAt(i-1) || p.charAt(j-2) == '.'))
                            dp[i][j] = dp[i][j-1] || dp[i][j-2] || dp[i-1][j-1] || dp[i-1][j];
                        else if(j > 1)
                            dp[i][j] = dp[i][j-2];
                        else
                            dp[i][j] = false;
                    }
                    else
                        dp[i][j] = false;
                }
            }
        }
        return dp[m][n];
    }