1. 首页

LeetCode 010. 正则表达式匹配

题目描述:

题目描述:

难度:Hard

相关话题:字符串动态规划回溯算法

给定一个字符串( s ) 和一个字符模式( p )。实现支持 '.''*' 的正则表达式匹配。

'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。

匹配应该覆盖整个 字符串( s ) ,而不是部分字符串。

说明:

  • s 可能为空,且只包含从 a-z 的小写字母。

  • p 可能为空,且只包含从 a-z 的小写字母,以及字符 .*

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:
s = "aa"
p = "a*"
输出: true
解释:'*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。

示例3:

输入:
s = "ab"
p = ".*"
输出: true
解释:".*" 表示可匹配零个或多个('*')任意字符('.')。

示例 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释:'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。

示例 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

Js中文网 – 前端进阶资源教程 www.javascriptC.com,typescript 中文文档
Javascript中文网是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js……等,以帮助开发者成长为愿景的社区


思路:

动态规划,dp[i][j]代表到索引[0,i]p是否能被索引[0,j]s匹配。

如果p[i]===s[j] || p[i]==='.',说明它们匹配,dp[i][j]=dp[i-1][j-1]

如果不匹配,但是p[i]==='*'

  1. 如果p的前一个能和当前s匹配并且dp[i][j-1]===true,说明*可以延长上一个的p来匹配当前的s
  2. 如果上面条件不符合,但是dp[i-2][j]===true,也就是说前2个的p能和当前s匹配,那么*可以作为数量0,相当与忽略前一个p
/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
  let pLen=p.length,sLen=s.length
  let dp=Array(pLen+1).fill().map(()=>Array(sLen+1).fill(false))

  for(let i=0;i<pLen+1;i++){
    for(let j=0;j<sLen+1;j++){
      if(i===0 && j===0){
        dp[i][j]=true
      }else if(p[i-1]==="*" && j===0){
        dp[i][j]=dp[i-2][j]
      }
    }
  }
  for(let i=1;i<pLen+1;i++){
    for(let j=1;j<sLen+1;j++){
      let r=i-1,c=j-1
      if(p[r]===s[c] || p[r]==='.'){
        dp[i][j]=dp[i-1][j-1]
      }else if(p[r]==="*"){
        if(((p[r-1]===s[c] || p[r-1]===".") && dp[i][j-1]) || dp[i-2][j])
          dp[i][j]=true
      }
    }
  }
  return dp[pLen][sLen]
};

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 010. 正则表达式匹配

链接:https://www.javascriptc.com/4369.html

« LeetCode 011. 盛最多水的容器
LeetCode 009. 回文数»
Flutter 中文教程资源

相关推荐

QR code