专栏首页前端小书童一天一大 leet(正则表达式匹配)难度:困难 DAY-20

一天一大 leet(正则表达式匹配)难度:困难 DAY-20

题目(难度:困难):

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

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

所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。

说明

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

示例

  • 示例 1
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
  • 示例 2
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 
      在这里前面的元素就是 'a'。
      因此,字符串 "aa" 可被视为 'a' 重复了一次。
  • 示例 3
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。
  • 示例 4
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个,这里 'c' 为 0 个, 'a' 被重复一次。
      因此可以匹配字符串 "aab"。
  • 示例 5
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

抛砖引玉

题目要求完成的逻辑为:

// p中只包含.*及a-z
new RegExp(p).test(s);
  • 采用逐位匹配
  • 假设知道了,s前i-1和p前j-1位是否匹配,当判断i位是否只需要知道i和j位是否配置
  • 如果匹配那字符串匹配的结果就和前i-1匹配的结果一样
  • 如果s与p都为空则返回true,则f[0][0] = true
  • f[i][j]为s的第n-1个字符与p的第j-1位匹配

i和j是否匹配的情况包括:

  1. s[i-1]等于p[j-1]
  2. p[j-1]为.
  3. p[j-1]为*
    • s[i-1]等于p[j-2]
    • s[p-2]等于.

匹配过程中字符匹配和.与字符匹配都比较简单,复杂的为*匹配

  • *结合字符 -> (0-n)字符
  • .结合* -> 任意长度任意字符

逐位匹配

p[j-1]为*

  • 匹配0个字符,拿s的前i字符与p的前j-2(排除末尾的

其前一个字符)个规则匹配

  • 匹配n个字符,拿s的第i字符与p的第j-1(排除末尾的

)匹配,匹配通过则s的第i位和第i-1位都可适用改规则

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
  let m = s.length, n = p.length, f = new Array(m + 1);
  for (let v = 0; v < m + 1; v++) f[v] = new Array(n + 1);
  f[0][0] = true;
  for (var i = 0; i <= m; ++i) {
    for (var j = 1; j <= n; ++j) {
      if (p.charAt(j - 1) == '*') {
        f[i][j] = f[i][j - 2];
        if (matches(s, p, i, j - 1)) {
          f[i][j] = f[i][j] || f[i - 1][j];
        }
      }
      else {
        if (matches(s, p, i, j)) {
          f[i][j] = f[i - 1][j - 1];
        }
      }
    }
  }
  function matches(s, p, i, j) {
    if (i == 0) {
      return false;
    }
    if (p.charAt(j - 1) == '.') {
      return true;
    }
    return s.charAt(i - 1) == p.charAt(j - 1);
  }
  return Boolean(f[m][n]);
}

其他解法

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
    if (s == null || p == null) return false
  let len1 = s.length, len2 = p.length
  let dp = new Array(len1 + 1)
  for (let i = 0; i < dp.length; i++)
    dp[i] = new Array(len2 + 1).fill(false) // 将项默认为false

  dp[0][0] = true
  for (let j = 1; j < len2 + 1; j++) {
    if (p[j - 1] == '*')
      dp[0][j] = dp[0][j - 2]
  }
  for (let i = 1; i < len1 + 1; i++) {
    for (let j = 1; j < len2 + 1; j++) {
      if (s[i - 1] == p[j - 1] || p[j - 1] == ".") {
        dp[i][j] = dp[i - 1][j - 1]
      } else if (p[j - 1] == "*") {
        if (s[i - 1] == p[j - 2] || p[j - 2] == ".")
          dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j]
        else
          dp[i][j] = dp[i][j - 2]
      }
    }
  }
  return dp[len1][len2] // len1长度的s串 是否匹配 len2长度的p串
};

  1. 如果p为空,s为空匹配,s非空不匹配;
  2. s非空,p == s || p == '.'时第一个字符匹配;
  3. (p+1) != '',则递归判断剩下的是否匹配 first_match && isMatch(++s, ++p)
  4. (p+1) == '*',则有两种情况匹配:
  • *匹配0个字符,s匹配剩下的,即isMatch(s, p+2)
  • *匹配1个字符,继续用p匹配剩下的s,即first_match && isMatch(s+1, p)
/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
  var isMatch = function (s, p) {
    if (p.length < 1) {
      return !s.length
    }
    var match = false

    if (s.length > 0 && (s[0] == p[0] || p[0] == '.')) {
      match = true
    }
    if (p.length > 1 && p[1] == '*') {
      return match && isMatch(s.slice(1), p) || isMatch(s, p.slice(2))
    } else {
      return match && isMatch(s.slice(1), p.slice(1))
    }
  }

本文分享自微信公众号 - 前端小书童(gaowenju_web)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-06-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 一天一大 lee(有效的括号)难度:简单-Day20200814

    给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

    前端小书童
  • 一天一大 leet(最长有效括号)难度:困难-Day20200704

    给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。

    前端小书童
  • 一天一大 leet(三角形最小路径和)难度:中等-Day20200715

    dp[i] = dp[0]xdp[i-1] + (dp[1]xdp[i-2]) + ... + (dp[i-2]xdp[1]) + dp[i-1]*dp[0]

    前端小书童
  • 一天一大 lee(有效的括号)难度:简单-Day20200814

    给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

    前端小书童
  • 操作系统基础-CPU虚拟化

    原文发布于微信公众号 - 云服务与SRE架构师社区(ai-cloud-ops),作者李勇。

    王录华
  • ABP框架使用拦截器动态配置租户过滤器

    最近项目要求在ABP框架中根据TenantId是否为空来配置是否禁用租户过滤器。ABP自身给我我们禁用租户过滤器的两种方法官方文档

    心莱科技雪雁
  • 使用Fundebug API 批量上传Source Map

    Fundebug 支持使用 Source Map 还原真正的错误位置。这样的话,开发者能够迅速定位出错的源代码。另外,Fundebug 还能够展示出错的代码块,...

    Fundebug
  • 深度残差网络+自适应参数化ReLU激活函数(调参记录3)

    https://blog.csdn.net/dangqing1988/article/details/105595917

    用户6915903
  • PHP中WEB典型应用技术

          2)、在浏览器端提供能够进行文件上传的表单。其实就是给表单添加属性:enctype=”multipart/form-data”;

    北国风光
  • Python玩转简书钻

    2018年11月15号,简书迎来大变革,取消了以往的积分制度,换为去中心化的简书钻,每日发放一万简书钻。首先,简书给出了获取钻石的途径:写文点赞,与以往的阅读,...

    罗罗攀

扫码关注云+社区

领取腾讯云代金券