1. 首页

LeetCode 044. 通配符匹配

题目描述:

难度:Hard

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

给定一个字符串( s ) 和一个字符模式( p ) ,实现一个支持 '?''*' 的通配符匹配。

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串(包括空字符串)。

两个字符串完全匹配 才算匹配成功。

说明:

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

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

示例1:

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

示例2:

输入:
s = "aa"
p = "*"
输出: true
解释:'*' 可以匹配任意字符串。

示例3:

输入:
s = "cb"
p = "?a"
输出: false
解释:'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

示例4:

输入:
s = "adceb"
p = "*a*b"
输出: true
解释:第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

示例5:

输入:
s = "acdcb"
p = "a*c?b"
输入: false

思路:

  • DP

dp[i][j]表示前ipattern是否能匹配前jstring

初始dp[0][0]=true,并且如果当前p[i]*,那么如果dp[i-1][j]true,那么dp[i][j]也为true,因为*可以匹配空字符串。

如果遇到?或者p[i]===s[j],说明可以匹配任意一个字符或者两者相等,检查上一次是否匹配,dp[i][j]=dp[i-1][j-1]

如果遇到**可以匹配任何位数的字符,

  • 如果上一个模板值已经能和s匹配,那么当前它也能匹配(作为空字符串),例如:s="ab"p="ab*"

  • 如果上一个字符串已经和当前模板匹配了,那么它也能匹配(作为任意长度的字符),例如:s="abcd"p="a*"

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:前端中文网是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
 * @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))
  dp[0][0]=true
  for(let i=1;i<pLen+1;i++){
    if(p[i-1]==='*' && dp[i-1][0]){
      dp[i][0]=true
    }
  }
  for(let i=1;i<pLen+1;i++){
    for(let j=1;j<sLen+1;j++){
      let pId=i-1,sId=j-1
      if(p[pId]==="?" || p[pId]===s[sId]){
        dp[i][j]=dp[i-1][j-1]
      }
      if(p[pId]==="*"){
        dp[i][j]=dp[i-1][j] || dp[i][j-1]
      }
    }
  }
  return dp[pLen][sLen]
};
  • 双指针

定义两个指针,pi对应pattern上的索引,si对应string上的索引,关键思想是遇到*,记录当前的位置,并不使用,等到后面无法匹配时,在去查看*的位置。

如果p[pi]===s[si] || p[pi]==="?"说明两者可以视为相等,si++pi++

如果p[pi]==='*',记录当前的sipi,继续检查;

如果不符合以上的条件,说明不匹配了,这时要回到上一次记录的*的位置,继续检查。

最后检查pi是否到达p的最后。

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
  let star=-1,pi=0,si=0,match=0
  while(si<s.length){
    if(pi<p.length && (p[pi]===s[si] || p[pi]==="?")){
      pi++
      si++
    }else if(pi<p.length && p[pi]==="*"){
      match=si
      star=pi
      pi++
    }else if(star!==-1){
      match++
      pi=star+1
      si=match
    }else{
      return false
    }
  }
  while(pi<p.length && p[pi]==="*"){
    pi++
  }
  return pi===p.length
};

看完两件小事

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

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

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

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

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

标题:LeetCode 044. 通配符匹配

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

« LeetCode 045. 跳跃游戏 II
类微信界面开发之RecyclerView»
Flutter 中文教程资源

相关推荐

QR code