Regular Expression Matching(Hard)

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

解题思路：动态规划

复杂度(340ms)

时间 O(NM) 空间 O(N)

仍然从待检字符串尾部向前扫描，设0≤j<s.length()，考虑对于子串s[j..s.length()-1]能够在正则表达式p找到匹配（match[j]）的条件为s[j+1...s.length()-1]匹配且s[j]也能够在pattern中找到匹配。如何判断“s[j]也能够在pattern中找到匹配”呢？需要分两种情况讨论，设i为pattern索引

• 若p[i]不为'*'，则进行单字符判断，当p[i]=='.'或p[i]==s[j]时match[j]成立
• p[i]为"*"，则match[j]成立的条件为p[i-1]=='.'或p[i-1]==s[j]。另外，在这种情况下若match[j]已经被置为true，就算p[i-1]=='.'||p[i-1]==s[j]不成立也应将其值保持，因为*出现时，其之前元素可以为0个。

public boolean isMatch(String s, String p) {
    boolean[] match = new boolean[s.length() + 1];
    match[s.length()] = true;

    for(int i = p.length() - 1; i >=0; i--){
        if(p.charAt(i) == '*' && i>0){
            //如果是星号，从后往前匹配
            for(int j = s.length() - 1; j >= 0; j--){
                match[j] = match[j] || (match[j + 1] && (p.charAt(i - 1) == '.' || (p.charAt(i - 1) == s.charAt(j)))); 
            }
            //记得把i多减一，因为星号是和其前面的字符配合使用的
            i--;
        } else {
            //如果不是星号，从前往后匹配
            for(int j = 0; j < s.length(); j++){
                match[j] = match[j + 1] && (p.charAt(i) == '.' || (p.charAt(i) == s.charAt(j)));
            }
            //只要试过了pattern中最后一个字符，就要把match[s.length()]置为false
            match[s.length()] = false;
        }
    }
    return match[0];
}