昆明做网站软件,开发公司组织员工办按揭,潜山做网站,wordpress 导航文字图片leetcode10正则表达式匹配 思路python 思路
难点1 如何理解特殊字符 ’ * ’ 的作用#xff1f; 如何正确的利用特殊字符 ’ . ’ 和 ’ * ’ #xff1f;
* 匹配零个或多个前面的那一个元素
a* 可表示的字符为不同数目的 a#xff0c;包括#xff1a;如何正确的利用特殊字符 ’ . ’ 和 ’ * ’
* 匹配零个或多个前面的那一个元素
a* 可表示的字符为不同数目的 a包括
0 个 a
a1 个 a
aa2 个 a
aaa3 个 a难点2 正则表达式匹配:一种在文本中查找特定模式的方法。 这道题的正则匹配规则主要是 ’ * 、 ’ . ’ 这两个特殊字符的使用。
如何利用现有数据结构 构造这个问题 按照规则有顺序从左到右来匹配一个字符串。 所谓匹配是要涵盖 整个 字符串 s的而不是部分字符串。
如果不考虑这两个特殊字符我们可以用二维数组来动态的表示两个字符串是否匹配。只有前面的数组匹配上后面的数组才可以继续匹配。 但现在要考虑 ’ * 、 ’ . ’ 这两个特殊字符。 p[j] ‘.’则 p[j]一定可以与 s[i]匹配成功此时有dp[i][j]dp[i−1][j−1] p[j] ‘*’则表示可对 p[j]的前一个字符 p[j−1]匹配或理解为复制任意次包括 0 次。
匹配0次意味着 p[j−1]和 p[j]不起作用 相当于在 p 中删去了 p[j−1]和 p[j] 此时有dp[i][j]dp[i][j−2]
匹配 1次意味着 p[j−1]和 p[j]组成了 1 个’a’若 s[i−11, …, i]p[j−1] 则 dp[i][j]可由 dp[i−1][j−2]转移而来 此时有dp[i][j]dp[i−1][j−2],s[i−11, …, i]p[j−1]
匹配 k 次意味着 p[j−1]和 p[j]组成了 k 个’a’若 s[i−k1, …, i]p[j−1] 则 dp[i][j]可由 dp[i−k][j−2]转移而来 此时有dp[i][j]dp[i−k][j−2],s[i−k1, …, i]p[j−1] 难点3 状态转移的优化 总的来看当 p[j] ’ 时对于匹配 0∼k次我们有 同时对于 dp[i−1][j]我们有 观察发现2式与1式中的后 k 项刚好相差了一个条件 s[i]p[j−1]将2式代入1式可得简化后的「状态转移方程」为 p[j] 时简化后对应的状态更新过程如下图所示
记 s 的长度为 mp的长度为 n 。为便于状态更新减少对边界的判断初始二维 dpdpdp 数组维度为 (m1)×(n1)其中第一行和第一列的状态分别表示字符串 s 和 p 为空时的情况。
显然dp[0][0]True。对于其他 dp[0][j]当 p[j]≠p[j]‘时s[0,…,j]无法与空字符匹配因此有 dp[0][j]False而当 p[j]p[j]p[j]’时则有 dp[0][j]dp[0][j−2]。
python
class Solution:def isMatch(self, s: str, p: str) - bool:m, n len(s), len(p)dp [[False] * (n1) for _ in range(m1)]# 初始化dp[0][0] Truefor j in range(1, n1):if p[j-1] *:dp[0][j] dp[0][j-2]# 状态更新for i in range(1, m1):for j in range(1, n1):if s[i-1] p[j-1] or p[j-1] .:dp[i][j] dp[i-1][j-1]elif p[j-1] *: # 【题目保证*号不会是第一个字符所以此处有j2】if s[i-1] ! p[j-2] and p[j-2] ! .:dp[i][j] dp[i][j-2]else:dp[i][j] dp[i][j-2] | dp[i-1][j]return dp[m][n]
