題目

給你一個輸入字符串 (s) 和一個字符模式 § ，請你實現(xiàn)一個支持 ‘?’ 和 ‘’ 匹配規(guī)則的通配符匹配：
‘?’ 可以匹配任何單個字符。
'’ 可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要條件是：字符模式必須能夠 完全匹配 輸入字符串（而不是部分匹配）。

示例 1：

輸入：s = “aa”, p = “a”
輸出：false
解釋：“a” 無法匹配 “aa” 整個字符串。
示例 2：

輸入：s = “aa”, p = ""
輸出：true
解釋：'’ 可以匹配任意字符串。
示例 3：

輸入：s = “cb”, p = “?a”
輸出：false
解釋：‘?’ 可以匹配 ‘c’, 但第二個 ‘a(chǎn)’ 無法匹配 ‘b’。

提示：

0 <= s.length, p.length <= 2000
s 僅由小寫英文字母組成
p 僅由小寫英文字母、‘?’ 或 ‘*’ 組成

思路

這個問題可以使用動態(tài)規(guī)劃來解決，其中 dp[i][j] 表示字符串 s 的前 i 個字符和模式 p 的前 j 個字符是否匹配。

解題思路如下：

1. 初始化動態(tài)規(guī)劃表 dp，大小為 (len(s) + 1) x (len(p) + 1)。

2. 初始化 dp[0][0] 為 True，表示空字符串與空模式匹配。

3. 對于模式 p 中的 *，因為 * 可以匹配任意字符序列（包括空字符序列），所以可以將 dp[0][j] 設(shè)置為 dp[0][j - 1]，即模式中的 * 可以匹配空字符串。

4. 開始動態(tài)規(guī)劃過程，遍歷 dp 表格，其中 dp[i][j] 的計算取決于以下情況：

   • 如果 s[i - 1] 和 p[j - 1] 相等，或者 p[j - 1] 是 ?，則 dp[i][j] = dp[i - 1][j - 1]。
   • 如果 p[j - 1] 是 *，則 dp[i][j] = dp[i - 1][j] || dp[i][j - 1]。這表示 * 可以匹配多個字符或者空字符串。

5. 最終，dp[len(s)][len(p)] 的值就表示整個字符串 s 是否與模式 p 完全匹配。

這個算法的時間復(fù)雜度是 O(m * n)，其中 m 是字符串 s 的長度，n 是模式 p 的長度。文章來源地址http://www.zghlxwxcb.cn/news/detail-660640.html

代碼

object Solution {
    def isMatch(s: String, p: String): Boolean = {
        val m = s.length
        val n = p.length
        val dp = Array.ofDim[Boolean](m + 1, n + 1)
        dp(0)(0) = true

        for (j <- 1 to n) {
            if (p(j - 1) == '*') {
                dp(0)(j) = dp(0)(j - 1)
            }
        }

        for (i <- 1 to m) {
            for (j <- 1 to n) {
                if (s(i - 1) == p(j - 1) || p(j - 1) == '?') {
                    dp(i)(j) = dp(i - 1)(j - 1)
                } else if (p(j - 1) == '*') {
                    dp(i)(j) = dp(i - 1)(j) || dp(i)(j - 1)
                }
            }
        }

        dp(m)(n)
    }

    def main(args: Array[String]): Unit = {
        val s1 = "aa"
        val p1 = "a"
        println(isMatch(s1, p1))  // 輸出 false

        val s2 = "aa"
        val p2 = "*"
        println(isMatch(s2, p2))  // 輸出 true

        val s3 = "cb"
        val p3 = "?a"
        println(isMatch(s3, p3))  // 輸出 false
    }
}

到了這里，關(guān)于leetcode-動態(tài)規(guī)劃-44-通配符匹配的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！