成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

LeetCode44.通配符匹配 JavaScript

Mr_houzi / 1350人閱讀

摘要：給定一個字符串和一個字符模式，實(shí)現(xiàn)一個支持和的通配符匹配?？梢云ヅ淙我庾址兆址?。兩個字符串完全匹配才算匹配成功。示例輸入輸出解釋第一個可以匹配空字符串第二個可以匹配字符串示例輸入輸入?yún)⒖紭?gòu)造函數(shù)執(zhí)行

給定一個字符串 (s) 和一個字符模式 (p) ，實(shí)現(xiàn)一個支持 "?" 和 "*" 的通配符匹配。

"?" 可以匹配任何單個字符。
"*" 可以匹配任意字符串（包括空字符串）。
兩個字符串完全匹配才算匹配成功。

說明:

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) {
    // 構(gòu)造 dp 函數(shù)
    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
    // 執(zhí)行
    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]
};

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/104723.html

相關(guān)文章

  • Leetcode 44 Wildcard Matching 通配符匹配

    摘要：難度題目給出一個字符串和一個要求我們給出這個字符串是否匹配這個其中通配符跟我們平常見到的一樣是和代表任意單個字符代表一個或多個字符這個題跟簡單正則匹配比較類似可以跟這里面第二個解法一樣采取類似的動態(tài)規(guī)劃解法在里取中間某個確定的字符串序列將字 Implement wildcard pattern matching with support for ? and *. ? Matches ...

    SimonMa 評論0 收藏0

  • 6-9月技術(shù)文章匯總

    摘要：分布式的管理和當(dāng)我在談?wù)摷軜?gòu)時我在談啥狀態(tài)碼詳解無狀態(tài)協(xié)議和請求支持哪些方法分層協(xié)議棧有哪些數(shù)據(jù)結(jié)構(gòu)運(yùn)用場景說說你常用的命令為什么要有包裝類面向?qū)ο蟮奶卣魇巧妒巧队惺裁春锰幭到y(tǒng)設(shè)計工程在線診斷系統(tǒng)設(shè)計與實(shí)現(xiàn)索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理軟技能 HTTP 【HTTP】分布式session的管理 【HTTP】Cookie和Session 【HTTP】當(dāng)我在談?wù)揜estFul架構(gòu)時我在談啥？...

    miya 評論0 收藏0

  • Leetcode 10 Regular Expression Matching 簡單正則匹配

    摘要：難度這道題要求我們實(shí)現(xiàn)簡單的正則表達(dá)式的匹配只要求普通字符的匹配了解正則的同學(xué)都清楚代表任意單個字符代表個或多個前面的字符比如可以匹配到空字符串也可以匹配等等題目還要求我們判定正則是否匹配給定的字符串要判定整個字符串而不是其中一部分匹配就算 Implement regular expression matching with support for . and *. . Matche...

    OnlyLing 評論0 收藏0

  • [Leetcode] Wildcard Matching 通配符匹配

    摘要：當(dāng)我們遇到一個時，因?yàn)橹罂赡芤嘶刂猎撐恢弥匦缕ヅ?，我們要將它的下?biāo)記錄下來，比如。但是，當(dāng)我們連續(xù)遇到兩次的情況，如何保證我還是能繼續(xù)匹配，而不是每次都退回導(dǎo)致循環(huán)呢所以我們還要記錄一個，用來記錄用上一個連續(xù)匹配到的中的下標(biāo)。 Wildcard Matching Implement wildcard pattern matching with support for ? and ...

    tainzhi 評論0 收藏0

  • leetcode-44. Wildcard Matching

    摘要：正則由于的存在，所以有多種狀態(tài)，中間狀態(tài)儲存都需要記錄下來。然后以這些狀態(tài)為動態(tài)的中轉(zhuǎn)，繼續(xù)判斷到最后。最后正則匹配字符串是否成功的判斷依據(jù)，就是正則字符串的最大，是否出現(xiàn)在遍歷到最后的狀態(tài)列表中。 題目闡釋： 正則匹配字符串，用程序?qū)崿F(xiàn) 關(guān)鍵理解： 正則匹配，動態(tài)規(guī)劃思想，一個個向后追溯，后面的依賴前面的匹配成功。 正則和待匹配的字符串長度不一，統(tǒng)一到正則字符串的index索引上，每...

    leanxi 評論0 收藏0

發(fā)表評論

0條評論

閱讀需要支付1元查看
<