LeetCode44.通配符匹配 JavaScript

Mr_houzi 發布于2019-08-23 18:08 / 1344人閱讀

摘要：給定一個字符串和一個字符模式，實現一個支持和的通配符匹配。可以匹配任意字符串包括空字符串。兩個字符串完全匹配才算匹配成功。示例輸入輸出解釋第一個可以匹配空字符串第二個可以匹配字符串示例輸入輸入參考構造函數執行

給定一個字符串 (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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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