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代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class12/Code04_RegularExpressionMatch.java)
需要在 Python 中使用正则表达式来匹配不以给定模式开头的字符串吗？
如果是这样，你可以使用下面的语法来查找所有的字符串，除了那些不以https 开始的字符串。
r"^(?!https).*"复制代码第一步：匹配不以模式开头的字符串在这个例子中，我们有一个 URL 的列表。假设你想得到所有不以https 开始的网址。
为了这个目的，我们将使用负数查找。
import retexts = ['https://en.wikipedia.org/wiki/Main_Page/','http://en.wikipedia.org/wiki/National_Park_Service/','https://en.wikipedia.org/wiki/Hoover_Dam/','http://en.wikipedia.org/wiki/United_States_Bureau_of_Reclamation/','https://en.wikipedia.org/wiki/Central_African_Republic/','en.wikipedia.org/wiki/Africa/','ftp://en.wikipedia.org/wiki/Central_African_Republic/',]for text in texts: print(re.findall(r"^(?!https).*", text))复制代码其结果是。
[]['http://en.wikipedia.org/wiki/National_Park_Service/'][]['http://en.wikipedia.org/wiki/United_States_Bureau_of_Reclamation/'][]['en.wikipedia.org/wiki/Africa/']['ftp://en.wikipedia.org/wiki/Central_African_Republic/']复制代码它是如何工作的？
^ - 断定位置在字符串的开头(?!https) - 负向查找 - 断言重码不匹配 - https.* - 匹配0到无限次之间的任何字符第2步：匹配不以几个模式开始的字符串现在，让我们试着找到所有不以......开头的字符串。
httpsftp我们可以使用| ，也就是在regex语法中 -r"^(?!https|ftp).*" 。
for text in texts: print(re.findall(r"^(?!https|ftp).*", text))复制代码结果是。
[]['http://en.wikipedia.org/wiki/National_Park_Service/'] []['http://en.wikipedia.org/wiki/United_States_Bureau_of_Reclamation/']
[]['en.wikipedia.org/wiki/Africa/' ][]
注意：你可以用| 添加许多模式。
第3步：匹配不以列表中的字符开始的字符串最后让我们看看如何匹配所有不以几个字符开头的字符串，比如。
fh这次我们要列出方括号内的所有字符：[^hf] 。语句[hf] 意味着匹配字母 -f 或h ，而^ 则否定匹配。
换句话说，匹配列表中不存在的单个字符 -[hf] 。
所以我们可以使用。
for text in texts: print(re.findall(r"^[^hf].*", text))复制代码这将给我们带来。
[][][][][]['en.wikipedia.org/wiki/Africa/'][]