题目

LeetCode.44.通配符匹配（困难）

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

‘?’ 可以匹配任何单个字符。
‘*’ 可以匹配任意字符串（包括空字符串）。

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

说明:

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

题解

从左到右遍历s和p做匹配，用双指针i、j分别做匹配。

p[j] == ?时，当作普通字符跟s[i]匹配就好了。

p[j] == *时：

匹配0个字符时，让s[i]跟p[j + 1]继续匹配。
匹配1个或多个字符时，让s[i + 1]跟p[j]继续匹配，因为*可以匹配多个字符。

边界处理

由于*是会匹配多个字符或0个字符的，如果p后面有很多个*，在i走到头后，j还没走到头的时候，对p尾部的*要做处理。

递归

class Solution {
    fun isMatch(s: String, p: String): Boolean {
        val m = s.length
        val n = p.length
        fun match(i: Int, j: Int): Boolean {
            if (j == n) return i == m
            if (i == m) {
                var k = j
                while (k < n && p[k] == '*') k++
                return k == n
            }
            val isCharMatch = s[i] == p[j] || p[j] == '?'
            return if (isCharMatch) match(i + 1, j + 1)
            else if (p[j] == '*') match(i, j + 1) || match(i + 1, j) // 匹配s中的0个或1个字符
            else false
        }
        return match(0, 0)
    }
}

自底向上动态规划

递归已经给出了状态转移方程。

设dp[i][j] 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配。

s[i - 1] == p[j - 1] || p[j - 1] == '?'时，直接匹配上了，dp[i][j] = dp[i - 1][j - 1]。
p[j - 1] == '*'时，匹配0个或1个字符，dp[i][j] = dp[i - 1][j] || dp[i][j - 1]。

边界处理：

p开头都是*时可以匹配空字符串，要单独处理一下。

class Solution {
    fun isMatch(s: String, p: String): Boolean {
        val m = s.length
        val n = p.length
        val dp = Array(m + 1) { BooleanArray(n + 1) { false } }
        // 空字符串跟空字符串可以匹配
        dp[0][0] = true
        // *可以匹配空字符串
        for (i in 1..n) {
            dp[0][i] = dp[0][i - 1] && p[i - 1] == '*'
        }
        for (i in 1..m) {
            for (j in 1..n) {
                dp[i][j] = when {
                    // 匹配1个字符
                    s[i - 1] == p[j - 1] || p[j - 1] == '?' -> dp[i - 1][j - 1]
                    // *匹配0个字符或1个字符
                    p[j - 1] == '*' -> dp[i][j - 1] || dp[i - 1][j]
                    else -> false
                }
            }
        }
        return dp[m][n]
    }
}