10 Regular Expression Matching

10. Regular Expression Matching

1. Question

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

2. Implementation

(1) Recursion

思路: 我们从后往前匹配，这样的方法好处是一旦我们遇到"*",由于*的在这里的特性是匹配前一个字符0至多次，这样的话我们只要检查*前的一个字符是否和当前p的字符相同即可。在从后往前匹配的过程中，我们将过程分成几个cases:

1.如果pIndex = -1时，说明我们已经匹配完p的所有字符，这时只有当sIndex也等于-1时我们才return true

2.如果p.charAt(pIndex) = ‘*’时

class Solution {
    public boolean isMatch(String s, String p) {
        return isMatch(s, s.length() - 1, p, p.length() - 1);
    }

    public boolean isMatch(String s, int sIndex, String p, int pIndex) {
        if (pIndex == -1) {
            return sIndex == -1;
        }
        if (p.charAt(pIndex) == '*') {
            if (sIndex >= 0 && (p.charAt(pIndex - 1) == '.' || p.charAt(pIndex - 1) == s.charAt(sIndex))) {
                if (isMatch(s, sIndex - 1, p, pIndex)) {
                    return true;
                }
            }
            return isMatch(s, sIndex, p, pIndex - 2);
        }

        if (sIndex >= 0 && (p.charAt(pIndex) == '.' || s.charAt(sIndex) == p.charAt(pIndex))) {
            return isMatch(s, sIndex - 1, p, pIndex - 1);
        }

       return false;
    }
}

(2) DP

3. Time & Space Complexity