2021-07-02：正则表达式匹配。给定一个字符串s和一个匹配串p。".“匹配单个字符。”"匹配左边元素的多个字符。判断p是否匹配s。比如s=“ab”,p=“a.”，返回true。比如s=“ab”,p="a"，返回false。比如s=“aaa”,p=“a*”，返回true。比如s=“moonfdd”,p="kmoonfdd"，返回true,因为""表示零个或者多个，这里’k’表示0个。
福大大 答案2021-07-02：
为了更好的处理边界问题。s和p都追加"1"。比如s="",p=“cc”，加1后s=“1”,p=“cc1”。方法1递归和方法2动态规划都会用到。
1.自然智慧，递归。会递归就行，思想很重要。会了递归，动态规划也就会了。
si指针指向s中某个位置，pi指针指向p中某个位置。
1.1.pi+1不带星。
si指针右移1位，pi指针右移1位。
1.2.pi+1带星。
si指针右移1位，pi指针右移2位。匹配的时候。
si指针右移1位，pi指针右移0位。匹配的时候。
si指针右移0位，pi指针右移2位。匹配的时候和不匹配的时候。
2.动态规划。时间复杂度是O(MN)，空间复杂度是O(MN)。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
s := "moonfdd"
p := "c*c*moonfddc*c*"
ret := isMatch(s, p)
fmt.Println(ret)
}
//递归
func isMatch(s string, p string) bool {
s = s + "1"
p = p + "1"
return process(s, 0, p, 0)
}
func process(s string, si int, p string, pi int) bool {
if si == len(s) && pi == len(p) {
return true
}
if si == len(s) || pi == len(p) {
return false
}
//pi+1是否是*
if pi+1 < len(p) && p[pi+1] == '*' {
if p[pi] == '.' || p[pi] == s[si] {
if process(s, si+1, p, pi) {
return true
}
if process(s, si+1, p, pi+2) {
return true
}
}
if process(s, si, p, pi+2) {
return true
}
} else {
if p[pi] == '.' || p[pi] == s[si] {
if process(s, si+1, p, pi+1) {
return true
}
}
}
return false
}
// 动态规划版本 + 斜率优化
func isMatch3(str string, pattern string) bool {
s := str + "1"
p := pattern + "1"
N := len(s)
M := len(p)
dp := make([][]bool, N+1)
for i := 0; i < N+1; i++ {
dp[i] = make([]bool, M+1)
}
dp[N][M] = true
for j := M - 1; j >= 0; j-- {
dp[N][j] = (j+1 < M && p[j+1] == '*') && dp[N][j+2]
}
// dp[0..N-2][M-1]都等于false，只有dp[N-1][M-1]需要讨论
if N > 0 && M > 0 {
dp[N-1][M-1] = s[N-1] == p[M-1] || p[M-1] == '.'
}
for i := N - 1; i >= 0; i-- {
for j := M - 2; j >= 0; j-- {
if p[j+1] != '*' {
dp[i][j] = ((s[i] == p[j]) || (p[j] == '.')) && dp[i+1][j+1]
} else {
if (s[i] == p[j] || p[j] == '.') && dp[i+1][j] {
dp[i][j] = true
} else {
dp[i][j] = dp[i][j+2]
}
}
}
}
return dp[0][0]
}
执行结果如下：
左神java代码
