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

分析及代码

可以用recursive和dp做，先说dp吧

• 定义: f(i,j)表示s[0,i)与p[0,j)能够匹配，因为有初始化，所以坐标i对应的是字符串里的i-1
• 转移方程：

if p[j - 1] != '*'
    f(i, j) = f(i - 1, j - 1) && s[i - 1] == p[j - 1]
else // p[j - 1] == '*'
    // '*' matches zero character
    f(i - 1, j - 2)
    or
    // '*' matches one or more characters
    f(i - 1, j) && s[i - 1] == p[j - 2]

理解辅助：
比如 

s = "ccb"
p = "cca*b"
现在两个string当前位都指向'b'这个位置
那么，p[j - 1] == '*'，并且此时*匹配了0个字符
所以我们期待s: “cc”和p: "cc"能够匹配，也就是s[i -1]和p[j - 2]匹配

s = "ccaab"
p = "cca*b"
现在两个string当前位都指向'b'这个位置
那么，p[j - 1] == '*'，并且此时*匹配了1+个字符
所以我们期待s: “cca”和p: "cca*"能够匹配，也就是s[i -1]和p[j - 2]匹配，
并且s[i-1]和p[j - 2]字符是匹配的，即s里倒数第二个‘a'，要和p里的a*里的'a'匹配

要注意的就是比较字符是否匹配，不仅可以是字符本身相等，也可以是p的该位为'.'

• 初始化：

boolean[sLength + 1][pLength + 1]

p == 0,但是s != 0, 都为false
因为s必须要匹配上pattern里的某一部分

s == 0, 如果p这位是*，并且f(0, j - 2)匹配上了，那可以为true
因为比如pattern: a*b*c*...虽然很长，但是都可以匹配空串

解释清楚了，就上代码吧

public boolean isMatch(String s, String p) {
    if(s == null || p == null) {
        return false;
    }
    int sl = s.length();
    int pl = p.length();
    boolean[][] record = new boolean[sl + 1][pl + 1];
    record[0][0] = true;
    for(int i = 1; i <= sl; i++) {
        record[i][0] = false;
    }
    for(int i = 1; i <= pl; i++) {
        record[0][i] = i > 1 && p.charAt(i - 1) == '*' && record[0][i - 2];
    }
    for(int i = 1; i <= sl; i++) {
        for(int j = 1; j <= pl; j++) {
            if(p.charAt(j - 1) != '*') {
                record[i][j] = record[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.');
            } else {
                record[i][j] = record[i][j - 2] || record[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.');
            }
        }
    }
    return record[sl][pl];
}

因为是动规填格子，所以复杂度是O(nm)

下面就是recursive，理解了动规，这个就比较容易了，因为会LTE，所以OJ里面没有ac

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

time complexity还木有研究，先上个连接 https://discuss.leetcode.com/topic/43493/what-is-time-complexity-of-recursive-solution/4