# 10. Regular Expression Matching (Facebook 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("abc", ".*") → true
isMatch("aab", "c*a*b") → true
```

## 思路
'.' 匹配任意单字符，但不能匹配空字符；'*' 可以匹配 0 或多个前面一个字符，匹配 0 个就是将前面的字符删掉，匹配多个代表对前面字符的重复。'*' 也可以匹配前面的 '.' 即 '.*' 可以代表一个 '.' 两个 '.' 或者多个 '.' 每一步匹配都会出现多种条件判别情况，我们用递归和动态规划来分别实现。

## 题解1: Recursion
定义一个 isMatch 递归函数进行匹配，两个变量：s 和 p。先对 p 做条件判断，在此基础上，对 s 做条件判断。

### 条件
1. p.length() == 0, s 为空返回 true，s 不空则返回 false。
2. p.length() == 1  
    (2-1) s 为空返回 false；  
    (2-2) s 不为空，p.charAt(0) == s.charAt(0) 或者 p.charAt(0) == '.'  
    若满足则返回 isMatch(s.substring(1), p.substring(1))，否则为 false。
3. P.length() >= 2  
    (3-1) s 不空，p.charAt(1) != '*'，且满足 s.charAt(0) == p.charAt(0) || p.charAt(0) == '.' 时，若满足则返回 isMatch(s.substring(1), p.substring(1))，否则为 false。
    (3-2) s 不空，P.length() >= 2 p.charAt(1) == '*'，且满足 s.charAt(0) == p.charAt(0) || p.charAt(0) == '.' 时，如果该字符只出现一次 if (isMatch(s, p.substring(2))) 返回 true，否则重复执行 s = s.substring(1)
    (3-3) p.charAt(1) == '*', 返回 isMatch(s, p.substring(2)). 由上述，我们把条件 2 的最后一种情况和条件 3 的第一种情况合并。

### Time
O((m+n)x2^(m+n/2)), m=s.length,n=p.length
### Space
O(m^2 + n^2)

### 代码如下：
```
class Solution {
    public boolean isMatch(String s, String p) {
        if (p.length()==0) {
            return s.length()==0;
        }
        if (p.length() == 1 || p.charAt(1) != '*') {
            if (s.isEmpty() || (p.charAt(0) != '.' && p.charAt(0) != s.charAt(0))){
                return false;
            } else {
                return isMatch(s.substring(1), p.substring(1));
            }
        }
        while (!s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')){
            if (isMatch(s, p.substring(2))) {
                return true;
            }
            s = s.substring(1);
        }
        return isMatch(s, p.substring(2));
    }
}
```

## 题解2: DP

定义一个 boolean dp[i][j]，用来表示 s[0-i] 与 p[0-j] 是否匹配。dp[0][0] 表示两个空字符串是否匹配，初始化为 true。dp[i][j] 为 true 的条件如下：

### 条件
1. s.charAt(i)=p.charAt(j)
2. p.charAt(j)='.'
3. p.charAt(j)='*'  
   (3-1) if p.charAt(j-1)!=s.charAt(i)， * matches zero of the preceding element. 
   (3-2) if p.charAt(j-1)==s.charAt(i)，或者 p.charAt(j-1) '.' * Matches one or more of the preceding element

### 注意⚠
如右图所示，考虑到这种情况("aab", "cab")中，c* 应匹配为空字符串，接下来应尝试匹配 aab 和 a*b。这个子问题的解决应从对应空字符串的匹配开始，即 dp[0][2] 应设为 true。

### Time
O(mn),m=s.length,n=p.length
### Space
O(mn)

### 代码如下：
```
class Solution {
  public boolean isMatch(String s, String p) {
    if (s == null || p == null) {
        return false;
    }
    boolean[][]dp=new boolean[s.length()+1][p.length()+1];
    dp[0][0]= true;
    for(int i=0;i<p.length();i++){  
        if(p.charAt(i)=='*'&& dp[0][i-1])
            dp[0][i+1]=true;
    }
    for(int i=0;i<s.length();i++){  
        for(int j=0;j<p.length();j++ ){  
            if(p.charAt(j)=='.'){  
                dp[i+1][j+1]=dp[i][j];
            }
            if(p.charAt(j)==s.charAt(i)){  
                dp[i+1][j+1]=dp[i][j];
            }
            if (p.charAt(j) == '*') {
                if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
                    dp[i+1][j+1] = dp[i+1][j-1];
                }
                else {
                    dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
                }
            }
        }
    }
    return dp[s.length()][p.length()];
  }
}
```