# 10. Regular Expression Matching

## Description

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 = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
``````

Example 4:

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

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

Tags: Math, String

## 题解

### 思路1

``````for i:=len(s); i>=0; i--{
for j:=len(p)-1; j>=0; j--{
// 检查每个匹配的第一个字母是否匹配
fm := false
if i<len(s) && (s[i]==p[j] || p[j]=='.') {
fm = true
}

// 当第二个字符模式中有*时
if (j+1)<len(p) && p[j+1]=='*' {
// 考虑*为0并且重合
// 如果不匹配，检查第一个匹配是否与[i + 1，j]匹配
dp[i][j] = dp[i][j+2] || (fm && dp[i+1][j])
//fmt.Println("a",i,j,dp[i][j])
}else{
dp[i][j] = fm && dp[i+1][j+1]
//fmt.Println("b",i,j,dp[i][j])
}
}
}
return dp
``````

}

``````
### 思路2
> 思路2
```go
``````