LeetCode44.通配符匹配 JavaScript

Mr_houzi 发布于2019-08-23 18:08 / 1348人阅读

摘要：给定一个字符串和一个字符模式，实现一个支持和的通配符匹配。可以匹配任意字符串包括空字符串。两个字符串完全匹配才算匹配成功。示例输入输出解释第一个可以匹配空字符串第二个可以匹配字符串示例输入输入参考构造函数执行

给定一个字符串 (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

参考

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
    // 构造 dp 函数
    let dp = []
    for (let i = 0; i <= s.length; i++) {
        let child = []
        for (let j = 0; j <= p.length; j++) {
            child.push(false)
        }
        dp.push(child)
    }
    dp[s.length][p.length] = true
    // 执行
    for (let i = p.length - 1; i >= 0; i--) {
        if (p[i] != "*") break
        else dp[s.length][i] = true
    }

    for (let i = s.length - 1; i >= 0; i--) {
        for (let j = p.length - 1; j >= 0; j--) {
            if (s[i] == p[j] || p[j] == "?") {
                dp[i][j] = dp[i + 1][j + 1]
            } else if (p[j] == "*") {
                dp[i][j] = dp[i + 1][j] || dp[i][j + 1]
            } else {
                dp[i][j] = false
            }
        }
    }
    return dp[0][0]
};

云服务器 GPU云服务器字符串通配符匹配算法 javascript分组匹配 LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/104723.html

Leetcode 44 Wildcard Matching 通配符匹配

摘要：难度题目给出一个字符串和一个要求我们给出这个字符串是否匹配这个其中通配符跟我们平常见到的一样是和代表任意单个字符代表一个或多个字符这个题跟简单正则匹配比较类似可以跟这里面第二个解法一样采取类似的动态规划解法在里取中间某个确定的字符串序列将字 Implement wildcard pattern matching with support for ? and *. ? Matches ...

SimonMa 2019-08-14 17:16 评论0 收藏0
6-9月技术文章汇总

摘要：分布式的管理和当我在谈论架构时我在谈啥状态码详解无状态协议和请求支持哪些方法分层协议栈有哪些数据结构运用场景说说你常用的命令为什么要有包装类面向对象的特征是啥是啥有什么好处系统设计工程在线诊断系统设计与实现索引背后的数据结构及算法原理软技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】当我在谈论RestFul架构时我在谈啥？...

miya 2019-07-30 18:03 评论0 收藏0
Leetcode 10 Regular Expression Matching 简单正则匹配

摘要：难度这道题要求我们实现简单的正则表达式的匹配只要求普通字符的匹配了解正则的同学都清楚代表任意单个字符代表个或多个前面的字符比如可以匹配到空字符串也可以匹配等等题目还要求我们判定正则是否匹配给定的字符串要判定整个字符串而不是其中一部分匹配就算 Implement regular expression matching with support for . and *. . Matche...

OnlyLing 2019-08-14 17:14 评论0 收藏0
[Leetcode] Wildcard Matching 通配符匹配

摘要：当我们遇到一个时，因为之后可能要退回至该位置重新匹配，我们要将它的下标记录下来，比如。但是，当我们连续遇到两次的情况，如何保证我还是能继续匹配，而不是每次都退回导致循环呢所以我们还要记录一个，用来记录用上一个连续匹配到的中的下标。 Wildcard Matching Implement wildcard pattern matching with support for ? and ...

tainzhi 2019-08-14 12:35 评论0 收藏0
leetcode-44. Wildcard Matching

摘要：正则由于的存在，所以有多种状态，中间状态储存都需要记录下来。然后以这些状态为动态的中转，继续判断到最后。最后正则匹配字符串是否成功的判断依据，就是正则字符串的最大，是否出现在遍历到最后的状态列表中。题目阐释：正则匹配字符串，用程序实现关键理解：正则匹配，动态规划思想，一个个向后追溯，后面的依赖前面的匹配成功。正则和待匹配的字符串长度不一，统一到正则字符串的index索引上，每...

leanxi 2019-07-30 17:20 评论0 收藏0