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="k*moonfdd"，返回true,因为"*"表示零个或者多个，这里'k'表示0个。

福大大 答案2021-07-02：

为了更好的处理边界问题。s和p都追加"1"。比如s="",p="c*c*"，加1后s="1",p="c*c*1"。方法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 mainimport "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代码]()