# 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的长度


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/oj-practices/chapter1/dynamic-programming/10-regular-expression-matching.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.