🧮 Algorithm Notebook
1、算法准备
1.1 牛客网编程OJ的典型输入输出
2、算法框架
2.1 动态规划
2.1.1 斐波那契数列
2.1.2 背包问题
2.1.3 贪心算法
2.1.4 序列和数组类问题
2.1.5 编辑距离
2.1.6 高楼扔鸡蛋
2.1.7 股票问题系列通解
2.1.8 最长有效括号
2.1.9 剪绳子
2.1.10 正则表达式匹配
2.2 二分查找
2.2.1 二分查找框架
2.2.2 搜索旋转排序数组
2.3 链表
2.3.1 反转链表
2.3.2 相交链表
2.3.3 合并链表
2.3.4 链表中倒数第k个节点
2.3.5 复制带随机指针的链表
2.4 排序算法
2.4.1 常见排序算法
2.5 二叉树
2.5.1 二叉树遍历
2.5.2 岛屿问题
2.5.3 二叉树路径问题
2.5.4 构造二叉树
2.6 回溯算法
2.6.1 回溯算法解题框架
2.6.2 N皇后
2.7 数组
2.7.1 删除有序数组中的重复项
2.7.2 滑动窗口最大值
2.7.3 调整数组顺序使奇数位于偶数前面
2.7.4 螺旋矩阵
2.7.5 多数元素
2.7.6 最大数
2.7.7 和为s的两个数字
2.7.8 构建乘积数组
2.7.9 两数之和
2.8 字符串
2.8.1 最小覆盖子串
2.8.2 比较版本号
2.8.3 验证IP地址
2.8.4 基本计算器 II
2.8.5 字符串解码
2.8.6 移掉 K 位数字
2.8.7 无重复字符的最长子串
2.8.8 第一个只出现一次的字符
2.8.9 翻转字符串里的单词
2.8.10 字符串转换整数 (atoi)
2.8.11 字符串四则运算
2.9 栈
2.9.1 最小栈
2.9.2 弹出序列
2.10 数学
2.10.1 用 Rand7() 实现 Rand10()
2.10.2 只出现一次的数字
2.10.3 整数反转
2.10.4 求1+2+…+n
2.10.5 二进制中1的个数
2.10.6 幂运算
2.10.7 1~n 整数中 1 出现的次数
2.10.8 数字序列中某一位的数字
2.10.9 丑数
2.10.10 n个骰子的点数
2.10.11 圆圈中最后剩下的数字
2.10.12 不用加减乘除做加法
2.10.13 x 的平方根
2.11 设计
2.11.1 LRU 缓存机制
-
+
tourist
register
Sign in
正则表达式匹配
## 1 题目 给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。 '.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素 所谓匹配,是要涵盖 整个 字符串 s 的,而不是部分字符串。 **示例 1:** ```txt 输入:s = "aa", p = "a" 输出:false 解释:"a" 无法匹配 "aa" 整个字符串。 ``` **示例 2:** ```txt 输入:s = "aa", p = "a*" 输出:true 解释:因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。 ``` **示例 3:** ```txt 输入:s = "ab", p = "." 输出:true 解释:"." 表示可匹配零个或多个('*')任意字符('.')。 ``` **提示:** * 1 <= s.length <= 20 * 1 <= p.length <= 30 * s 只包含从 a-z 的小写字母。 * p 只包含从 a-z 的小写字母,以及字符 . 和 *。 * 保证每次出现字符 * 时,前面都匹配到有效的字符 ## 2 问题分析 1. 本题中**点号通配符其实很好实现**,$s$**中的任何字符**,**只要遇到 $.$ 通配符**,**无脑匹配就完事了**,**主要是这个 $*$ 通配符不好实现**,**一旦遇到 $*$ 通配符**,**前面的那个字符可以选择重复一次**,**可以重复多次**,**也可以一次都不出现**,**针对这个问题**,**我们可以对所有可能出现的情况**,**全部都穷举一遍**,**只要有一种情况可以完成匹配**,**就认为 $p$ 可以匹配 $s$**,**那么一旦涉及两个字符串的穷举**,**我们就应该条件反射地想到动态规划的技巧了**。 2. 我们先脑补一下,**$s$ 和 $p$ 相互匹配的大致过程是两个指针 $i, j$ 分别在 $s$ 和 $p$ 上移动**,**如果最后两个指针都能移动到字符串的末尾**,**那么就匹配成功**,**反之则匹配失败**。 3. **正则表达算法问题只需要把握住一个基本点**,**看两个字符是否匹配**,**一切逻辑围绕匹配/不匹配两种情况展开即可**: 1. **如果不考虑 $*$ 通配符**,**面对两个待匹配字符串 $s[i]$ 和 $p[j]$**,**我们唯一能做的就是看他俩是否匹配**: ```java bool isMatch(string s, string p) { int i = 0, j = 0; while (i < s.size() && j < p.size()) { // 「.」通配符就是万金油 if (s.charAt(i) == p.charAt(i) || p.charAt(j) == '.') { // 匹配,接着匹配 s[i+1..] 和 p[j+1..] i++; j++; } else { // 不匹配 return false; } } return i == j; } ``` 2. 那么,考虑一下,**如果加入$*$通配符**,**局面就会稍微复杂一些**,不过只要分情况来分析,也不难理解: 1. **当$p[j + 1]$为$*$通配符时**,**我们分情况讨论下**: 1. **如果匹配**,**即$s.charAt(i) = p.charAt(j)$**,**那么有两种情况**: 1. $p.charAt(j)$**匹配多个字符**,比如$s = "aaa", p = "a*"$,**那么$p.charAt(0)$会通过$*$匹配3个字符$a$。** 2. $p.charAt(j)$**匹配0个字符**,比如$s = "aa", p = a*aa$**,***由于后面的字符可以匹配$s$**,**所以$p.charAt(0)$只能匹配0次**。 2. **如果不匹配**,**即$s.charAt(i) \ne p.charAt(j)$**,**只有一种情况**: 1. $p.charAt(j)$**只能匹配0次**,**然后看下一个字符是否能和$s.charAt(i)$匹配**,比如说$s = "aa", p = "b*aa"$,**此时$p.charAt(0)$只能匹配0次**。 3. 综上,我们可以**把之前的代码针对$*$通配符进行一下改造**: ```java if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') { // 匹配 if (j < p.size() - 1 && p.charAt(j + 1) == '*') { // 有 * 通配符,可以匹配 0 次或多次 } else { // 无 * 通配符,老老实实匹配 1 次 i++; j++; } } else { // 不匹配 if (j < p.size() - 1 && p.charAt(j + 1) == '*') { // 有 * 通配符,只能匹配 0 次 } else { // 无 * 通配符,匹配无法进行下去了 return false; } } ``` 2. 整体的思路应该很清晰了,但现在的问题时,**遇到通配符$*$时**,**到底应该是匹配0次还是匹配多次**,**多次是几次**,**这就是一个做【选择】的问题**,**要把所有可能的选择都穷举一遍才能得出结果**,**动态规划的核心就是【状态】和【选择】**,**【状态】无非就是$i$和$j$两个指针的位置**,**【选择】就是$p.charAt(j)$选择匹配几个字符**。 3. **根据【状态】**,**我们可以定义一个$dp$函数**,**其中$dp(s, i, p, j)$表示$s[i...]$是否可以匹配$p[j...]$**: ```java public boolean dp(String s, int i, String p, int j) ``` 4. **根据这个定义**,**我们想要的答案就是$i = 0, j = 0$时$dp$函数的结果**,**所以可以这样使用这个$dp$函数**: ```java public boolean isMatch(String s, String p) { // 指针 i, j 从索引 0 开始移动 return dp(s, 0, p, 0); } ``` 5. **可以根据之前的代码写出$dp$函数的主要逻辑**: ```java public boolean dp(String s, int i, String p, int j) { int m = s.length(), n = p.length(); if (j == n) {return i == m;} if (i == m) { // 如果能匹配空串,一定是字符和 * 成对出现 if (((n - j) % 2) == 1) {return false;} // 检查是否为 x*y*z* 这种形式 for (; j + 1 < n; j += 2) { if (p.charAt(j + 1) != '*') {return false;} } return true; } // 如果备忘录中存在,直接从备忘录中取 String key = String.format("%s_%s", i, j); if (memo.containsKey(key)) {return memo.get(key);} if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') { // 匹配 if (j < n - 1 && p.charAt(j + 1) == '*') { // * 匹配 0 次或多次 res = dp(s, i, p, j + 2) || dp(s, i + 1, p, j); } else { // * 常规匹配 1 次 res = dp(s, i + 1, p, j + 1); } } else { // 不匹配 if (j < n - 1 && p.charAt(j + 1) == '*') { // * 匹配 0 次 res = dp(s, i, p, j + 2); } else { // 无法继续匹配 res = false; } } // 将当前结果计入备忘录 memo.put(key, res); return res; } ``` 6. **根据$dp$函数的定义**,**上面的几种情况都很好解释**: 1. **当前字符可以匹配**: 1. **通配符匹配0次或多次**: 1. **将$j$加2**,$i$**不变**,**含义就是直接跳过$p.charAt(j)$和之后的通配符**,**即通配符匹配0次**。 ![图片](/media/202202/2022-02-13_1511410.7641277856847676.png) 2. **将$i$加1**,$j$**不变**,**含义就是$p.charAt(j)$匹配了$s.charAt(i)$**,**但$p.charAt(j)$还可以继续匹配**,**即通配符匹配多次的情况**。 ![图片](/media/202202/2022-02-13_1514110.2020226863039436.png) 3. **上面两种情况只要有一种可以完成匹配即可**,**所以对上面两种情况求或运算**。 2. **常规匹配1次**: 1. **由于这个条件分支是无$*$的常规匹配**,**那么如果$s.charAt(i) == p.charAt(j)$**,**就是$i$和$j$分别加1**。 ![图片](/media/202202/2022-02-13_1517130.4059230763448286.png) 2. **当前字符不可以匹配**: 1. **通配符匹配0次**: 1. **类似于上面的当前字符可以匹配时通配符匹配0的情况**,**将$j$加2**,**$i$不变**。 ![图片](/media/202202/2022-02-13_1523160.06426259020298242.png) 2. **没有$*$通配符**: 1. **如果无法匹配**,**也没有$*$通配符**,**那只能说明匹配失败了**。 ![图片](/media/202202/2022-02-13_1525000.6853264208756238.png) 7. 下面我们**考虑一下$dp$函数的$base \; case$**: 1. **一个$base \; case$是$j == p.size()$时**,**按照$dp$函数的定义**,**这意味着模式串$p$已经被匹配完了**,**那么应该看看文本串$s$匹配到哪里了**,**如果$s$也恰好被匹配完**,**则说明匹配成功**: ``` if (j == p.size) {return i == s.size();} ``` 2. 另一个$base \; case$是$i = s.size()$时,按照$dp$函数的定义,这种情况意味着文本串$s$已经全部被匹配完了,此时并不能根据$j$是否等于$p.size()$来判断是否完成匹配,只要$p[j...]$能够匹配空串,就可以算完成匹配,比如说$s = "a", p = "ab*c*"$,当$i$走到$s$末尾的时候,$j$并没有走到$p$的末尾,但是$p$依然可以匹配$s$,代码中使用了一个哈希表$memo$作为备忘录来减少重复遍历问题: ``` int m = s.length(), n = p.length(); if (j == n) {return i == m;} if (i == m) { // 如果能匹配空串,一定是字符和 * 成对出现 if (((n - j) % 2) == 1) {return false;} // 检查是否为 x*y*z* 这种形式 for (; j + 1 < n; j += 2) { if (p.charAt(j + 1) != '*') {return false;} } return true; } // 如果备忘录中存在,直接从备忘录中取 String key = String.format("%s_%s", i, j); if (memo.containsKey(key)) {return memo.get(key);} if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') { // 匹配 if (j < n - 1 && p.charAt(j + 1) == '*') { // * 匹配 0 次或多次 res = dp(s, i, p, j + 2) || dp(s, i + 1, p, j); } else { // * 常规匹配 1 次 res = dp(s, i + 1, p, j + 1); } } else { // 不匹配 if (j < n - 1 && p.charAt(j + 1) == '*') { // * 匹配 0 次 res = dp(s, i, p, j + 2); } else { // 无法继续匹配 res = false; } } // 将当前结果计入备忘录 memo.put(key, res); return res; ``` ## 3 参考代码 ```java // 最终结果 boolean res; // 备忘录 HashMap<String, Boolean> memo = new HashMap<>(); /** * 10. 正则表达式匹配 * @param s 字符串 * @param p 正则表达式 * @return p 是否可以匹配 s */ public boolean isMatch(String s, String p) { // 指针 i, j 从索引 0 开始移动 return dp(s, 0, p, 0); } /** * dp 函数 * @param s 文本串 * @param i 文本串索引 * @param p 模式串 * @param j 模式串索引 * @return p[j:] 是否可以匹配 s[i:] */ public boolean dp(String s, int i, String p, int j) { int m = s.length(), n = p.length(); if (j == n) {return i == m;} if (i == m) { // 如果能匹配空串,一定是字符和 * 成对出现 if (((n - j) % 2) == 1) {return false;} // 检查是否为 x*y*z* 这种形式 for (; j + 1 < n; j += 2) { if (p.charAt(j + 1) != '*') {return false;} } return true; } // 如果备忘录中存在,直接从备忘录中取 String key = String.format("%s_%s", i, j); if (memo.containsKey(key)) {return memo.get(key);} if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') { // 匹配 if (j < n - 1 && p.charAt(j + 1) == '*') { // * 匹配 0 次或多次 res = dp(s, i, p, j + 2) || dp(s, i + 1, p, j); } else { // * 常规匹配 1 次 res = dp(s, i + 1, p, j + 1); } } else { // 不匹配 if (j < n - 1 && p.charAt(j + 1) == '*') { // * 匹配 0 次 res = dp(s, i, p, j + 2); } else { // 无法继续匹配 res = false; } } // 将当前结果计入备忘录 memo.put(key, res); return res; } ``` ## 参考文献 1. [10. 正则表达式匹配](https://leetcode-cn.com/problems/regular-expression-matching)。 2. [东哥手写正则通配符算法,结构清晰,包教包会!](https://mp.weixin.qq.com/s/rnaFK05IcFWvNN1ppNf2ug)
ricear
Feb. 13, 2022, 3:38 p.m.
©
BY-NC-ND(4.0)
转发文档
Collection documents
Last
Next
手机扫码
Copy link
手机扫一扫转发分享
Copy link
Markdown文件
share
link
type
password
Update password