# Regular Expression Matching

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
```

## Analysis

Two string / array comparison, and it has subproblems that could lead to Dynamic Programming solution.

`isMatch(char[] str, char[] pattern)`

**State:**

`dp[i][j]`

Defined as `new boolean[str.length + 1][pattern.length + 1]`

The first `i` characters in the `str[]` matches first `j` characters in `pattern[]`

Note: the corresponding index (subscript) will be `i - 1` in `str[]`, `j - 1` in `pattern[]`

**Initialization:**

Assumption: `'*'` will never be the first character

`dp[0][0] = true` - no chars chosen from either of the string / char array, should match

then for `dp[0][i]` (for `a*` case):

```java
for (int i = 1; i <= pattern.length; i++) {
    if (pattern[i-1] == '*') {
        dp[0][i] = dp[0][i-2];
    }    
}
```

**State Transfer Function:**

1. if `p.charAt(j) == s.charAt(i)` : `dp[i][j] = dp[i-1][j-1]`
2. if `p.charAt(j) == '.'`: `dp[i][j] = dp[i - 1][j-1]`
3. if `p.charAt(j) == '*'` : sub conditions
   1. if `p.charAt(j-1) != s.charAt(i)` : `dp[i][j] = dp[i][j-2]` // in this case,  `a*`  only counts as empty
   2. if `p.charAt(j-1) == s.charAt(i)` or `p.charAt(j - 1) == '.'`:
      1. `dp[i][j]= dp[i-1][j]`  // in this case, `a*` counts as multiple `a`
      2. (*REDUNDANT*) or `dp[i][j] = dp[i][j-1]` // in this case, `a*` counts as single `a`
      3. or `dp[i][j] = dp[i][j-2]`  // in this case, `a*` counts as empty

**Answer:**

`dp[m][n]`

另：中文解释 From [@caiconghuai GitHub](https://github.com/caiconghuai/leetcode/tree/master/topics/Dynamic%20Programming/010.%20Regular%20Expression%20Matching):

> 在正则表达式中，由于不同的字符会有不同的匹配规则，其中`.`和`*`比较特别，需要对这两类字符进行分类讨论。
>
> * **定义状态**
>
>   `dp[i][j]` - 表示输入串长度为i，模式串长度为j时，是否能匹配。
> * **初始化状态值**：
>   * 输入串为空，模式串为空：`dp[0][0]` 必然可以匹配，即 `dp[0][0]=true`
>   * 输入串非空，模式串为空：由于模式串为空，此时必然不可匹配，即`dp[i][0]=false,` `i > 0`
>   * 输入串为空，模式串非空：此时如果模式串中有`*`，则是可以匹配0个前面的字符的，所有我们通过条件 `p.charAt(j-1) == '*' && dp[0][j-2]` 来判断是否可匹配
> * **转移方程**，转移方程表示通过已知的状态值来求解未知的状态值，在这里就是我们要求解
>
>   `dp[i][j]`，但是对于所有长度小于`i`的输入串和长度小于`j`的模式串，我们已知其匹配情况。现在，我们怎么利用前面的信息，来得到`dp[i][j]`的值。我们首先需要分析模式串的当前字符来做判断:
>
>   * `p.charAt(j-1) == s.charAt(i-1)`当前模式串字符一样，可以将当前字符匹配掉，然后状态转化如下: `dp[i][j] = dp[i-1][j-1];`
>   * `p.charAt(j-1) == '.'`当前模式串字符为`.`，可以匹配任意的字符，可以将当前输入串字符匹配掉，然后状态转化为:`dp[i][j] = dp[i-1][j-1]`
>   * `p.charAt(j-1) == '*'`由于`*`可以匹配0个或多个它的上一个字符，所以根据上一个字符的不同还需要做不同的分析：
>     * `p.charAt(j-2) != s.charAt(i-1) && p.charAt(j-2) != '.'`，这种情况说明上一个字符即不是`.`，也不和输入串的当前字符一样，所有无法用一个或多个上一个字符对输入串进行匹配，此时`*`只能匹配0个上一个字符: `dp[i][j] = dp[i][j-2];`
>     * 如果是这个条件里，说明上一个字符和输入串的当前字符是可以进行匹配的，故此时`*`即可以匹配0个前一个字符，也可以匹配1个前一个字符，也可以匹配多个前一个字符: `dp[i][j] = (dp[i][j-1] || dp[i-1][j] || dp[i][j-2])`  Note: 这种情况，也可以用`dp[i][j] = (dp[i-1][j] || dp[i][j-2])`

## Solution

**DP Solution (12ms 97% AC)**

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

        dp[0][0] = true;
        // Deals with patterns like a* or a*b* or a*b*c*
        for (int i = 1; i < n + 1; i++) {
            // Assumption: '*' will never be the first character
            if (pattern[i-1] == '*') {
                dp[0][i] = dp[0][i - 2];
            }
        }

        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (pattern[j - 1] == '.' || pattern[j - 1] == text[i - 1]) {
                    dp[i][j] = dp[i-1][j-1];
                } else if (pattern[j - 1] == '*')  {
                    dp[i][j] = dp[i][j - 2];
                    if (pattern[j-2] == '.' || pattern[j - 2] == text[i - 1]) {
                        dp[i][j] = dp[i][j] | dp[i - 1][j];
                    }
                } else {
                    dp[i][j] = false;
                }
            }
        }
        return dp[m][n];
    }
}
```

DP - Reference

```java
class Solution {
    //dp[i][j] first ith characters match jth characters
    // abc
    // ab.
    // ab*
    //initial dp[0][0] = true; dp[][0] = false;
    public boolean isMatch(String s, String p) {
        if(s == null || p == null){
            return false;
        }
        boolean[][] dp = new boolean[s.length() +1 ][p.length() + 1];
        for(int i = 0; i <= s.length(); i++){
            for(int j = 0;j <= p.length(); j++){
                if(i == 0 && j == 0){
                    dp[i][j] = true;
                    continue; //这个地方不能少了continue
                }
                if(j == 0){
                    dp[i][j] = false;
                    continue;//contiue不能少了
                }
                //dp[i][j] = false; // 默认false 不能没了
                if(p.charAt(j - 1) != '*'){
                    if(i > 0 && (p.charAt(j-1) == '.' || p.charAt(j-1) == s.charAt(i-1)))
                        dp[i][j] |= dp[i-1][j-1];
                }
                else{
                    if(j > 1)
                        dp[i][j] |= dp[i][j-2];
                    if(i > 0 && (p.charAt(j-2) == '.' || s.charAt(i-1) == p.charAt(j-2))){
                        dp[i][j] |= dp[i-1][j];
                    }
                }               
            }
        }
        return dp[s.length()][p.length()];
    }
}
```

## Reference

<https://leetcode.com/problems/regular-expression-matching/discuss/5847/Evolve-from-brute-force-to-dp>

<https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/RegexMatching.java>

<https://leetcode.com/articles/regular-expression-matching/>

[https://github.com/caiconghuai/leetcode/tree/master/topics/Dynamic Programming/010. Regular Expression Matching](https://github.com/caiconghuai/leetcode/tree/master/topics/Dynamic%20Programming/010.%20Regular%20Expression%20Matching)


---

# 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://aaronice.gitbook.io/lintcode/dynamic_programming/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.