江苏龙网

  1. 主页 > 生活百科 > >

算法：正则表达式匹配

正则表达式

请实现一个函数用来匹配包含'. '和'*'的正则表达式 。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次） 。在本题中，匹配是指字符串的所有字符匹配整个模式 。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配 。
示例1

  • 输入: s = "aa"，p = "a"
  • 输出: false
  • 解释: "a" 无法匹配 "aa" 整个字符串 。
示例2
  • 输入: s = "aaa"，p = "ab*.*"
  • 输出: true
  • 解释: 因为 '*' 表示零个或多个，这里 'b' 为 0 个, '.' 为 a , 重复2次 。因此可以匹配字符串 "aaa" 。
提示
  • s 可能为空，且只包含从 a-z 的小写字母 。
  • p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*' 。
方法：动态规划
算法：正则表达式匹配

文章插图
 
以示例2为例讲解：
  • 初始化取 dp[0][0] = true，代表匹配成功；
  • 当s取“a”的时候：p取“a”时候，成功；
  • p取“ab”的时候，失败；
  • p取“ab*”时候，*出现 0 次，即为 p 取 “a” 时候，成功；
  • p取“ab*.”的时候，失败，因为 s 只有一个字母，“.” 可以是任意字母，不满足；
  • p取“ab*.*”的时候，“.” 出现 0 次，“b”出现 0 次，成功 。
  • 以此类推……
 
代码如下：
算法：正则表达式匹配

文章插图
 
复杂度分析
  • 时间复杂度：O(MN)，其中 M,N 分别为 s 和 p 的长度，状态转移需遍历整个 dp 矩阵 。
  • 空间复杂度：O(MN)，状态矩阵 dp 使用 O(MN) 的额外空间 。
END本文内容出处是力扣官网，希望和大家一起刷算法，在后面的路上不变秃但是变强！

【算法：正则表达式匹配】


    推荐阅读


    上一篇：图扑 Web 可视化引擎在仿真分析领域的应用

    下一篇：探寻 Java 文件上传流量层面 waf 绕过