四时宝库

程序员的知识宝库

「Leetcode简洁笔记」第10题:正则表达式匹配

困难 警告!

想都不要想,直接看答案

本文答案参考自leetcode官方

【方法一】动态规划(DP)

动态规划的一般解法:

  1. 创建二维数组存放某些东西
  2. 确定状态转移方程
  3. 确定边界条件
  4. 开始

对这道题,这个二维数组 f[i][j] 表示 s 的前 i 个字符与 p 中的前 j 个字符是否能够匹配

  1. 如果 s 的第 i 个字符与 p 的第 j 个字符相同,则 f[i][j] = f[i - 1][j - 1] ,因为你后面匹配了那前面也肯定匹配
  2. 如果 s 的第 i 个字符与 p 的第 j 个字符不相同,则 f[i][j] = false
  3. 如果 p 的第 j 个字符是 *,在匹配不到(0次)的情况下, f[i][j] = f[i][j - 2],即星号和前面的字符相当于不存在(不影响结果)
  4. 如果 p 的第 j 个字符是 *,在匹配到 1次 的情况下 ,f[i][j] = f[i][j - 2]
  5. 如果 p 的第 j 个字符是 *,在匹配到(多于1次,设为n)的情况下 f[i][j] = f[i - n][j - 2],同样是因为后面匹配了那前面也肯定匹配,这里具体操作是循环执行 f[i][j] = f[i - 1][j] n - 1次,然后执行 f[i][j] = f[i][j - 2],官方给出了精巧的状态转移方程:(我难以表达出其精巧之处,反正就是精巧)
  1. 如果 p 的第 j 个字符是 . ,则必定匹配

最终状态转移方程为:


这里最好结合画图来理解(但是我懒~)

边界条件为:f[0][0] = true

答案为 f[m][n] ,其中 m 和 n 分别是字符串 s 和 p 的长度


因为本人水平有限,如果以上内容有误,不用走程序,直接骂吧~[捂脸]

发表评论:

控制面板
您好,欢迎到访网站!
  查看权限
网站分类
最新留言
    友情链接