> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/dynamic-programming/10-regular-expression-matching.md).

# 10     Regular Expression Matching

## 10. [Regular Expression Matching](https://leetcode.com/problems/regular-expression-matching/description/)

## 1. Question

Given an input string (`s`) and a pattern (`p`), 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).

**Note:**

* `s`could be empty and contains only lowercase letters`a-z`.
* `p`could be empty and contains only lowercase letters`a-z`, and characters like `.`or `*`.

**Example 1:**

```
Input:

s = "aa"
p = "a"

Output:
 false

Explanation:
 "a" does not match the entire string "aa".
```

**Example 2:**

```
Input:

s = "aa"
p = "a*"

Output:
 true

Explanation:
 '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
```

**Example 3:**

```
Input:

s = "ab"
p = ".*"

Output:
 true

Explanation:
 ".*" means "zero or more (*) of any character (.)".
```

**Example 4:**

```
Input:

s = "aab"
p = "c*a*b"

Output:
 true

Explanation:
 c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".
```

**Example 5:**

```
Input:

s = "mississippi"
p = "mis*is*p*."

Output:
false
```

## 2. Implementation

**(1) Recursion**

思路: 这题要分清况讨论

* 如果p是空，则查看s是否为空
* 如果p长度大于1且p\[1] == \*, 因为这里的\*必须匹配前面的字符0次或多次
  1. 如果匹配0次的话，就继续递归地比较s和p.substring(2)

     2.如果匹配多次，则需要s\[0] == p\[0] 或者 p\[0] == '.'， 然后递归地比较s.substring(1)和p
* 如果上述情况都不成立的话，则在s\[0] == p\[0] 或者 p\[0] == '.'的情况下，递归比较s.substring(1)和p.substring(1)

```java
class Solution {
    public boolean isMatch(String s, String p) {
        if (p.length() == 0) {
            return s.length() == 0;
        }

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

**（2）DP**

思路:

1. P\[i]\[j] = P\[i - 1]\[j - 1], if p\[j - 1] != '\*' && (s\[i - 1] == p\[j - 1] || p\[j - 1] == '.');
2. P\[i]\[j] = P\[i]\[j - 2], if p\[j - 1] == '\*' and the pattern repeats for 0 times;
3. P\[i]\[j] = P\[i - 1]\[j] && (s\[i - 1] == p\[j - 2] || p\[j - 2] == '.'), if p\[j - 1] == '\*' and the pattern repeats for at least 1 times.

```java
class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;

        // s要从0开始，因为s的开头可以被*看为空，如果*表示不匹配之前的character
        for (int i = 0; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (j > 1  && p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2] || (i > 0 && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') && dp[i - 1][j]);
                }
                else {
                    dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.');
                }
            }
        }
        return dp[m][n];
    }
}
```

## 3. Time & Space Complexity

**Recursion:** 时间复杂度O(2^n), 因为，假设P全是a\*a\*a\*这样组成，s = aaaaaaaa 而s的每一个字符都有2种可能：与当前的a\*匹配,或者与下一个a\*匹配（前一个匹配空), 这样假设s有n个字符，则实际上的复杂度是2^n, 空间复杂度O(L), L是s的长度