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
根据要求匹配字符
用dp,
```go func isMatch(s string, p string) bool { // DP解法 dp := make([][]bool, len(s)+1) for i:=0; i<len(s)+1; i++ { dp[i] = make([]bool, len(p)+1) } dp[len(s)][len(p)] = true
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[0][0]
}
### 思路2
> 思路2
```go
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：awesome-golang-algorithm