LeetCode44.通配符匹配 JavaScript

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

'?' 可以匹配任何单个字符。

'*' 可以匹配任意字符串（包括空字符串）。

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

说明:

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

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

示例 1:

示例 2:

示例 3:

示例 4:

示例 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]
};