题目描述

通配符匹配 问题是一种字符串匹配问题，其中模式字符串可以包含两种特殊字符：

• ?：表示可以匹配任何单个字符。
• *：表示可以匹配零个或多个前面的那一个元素（注意是前面的那一个元素，不是前面的所有元素）。

给定一个字符串 s 和一个模式字符串 p，实现一个函数来判断 s 是否能够和 p 匹配。

示例

示例 1:

输入: s = "aa", p = "a*"
输出: true
解释: '*' 表示零个或多个 'a'。因此，'aa' 可以被 'a*' 匹配。

示例 2:

输入: s = "ab", p = ".*"
输出: true
解释: '.*' 表示首先匹配任意单个字符（'a'），然后匹配零个或多个任意字符（'b'）。

示例 3:

输入: s = "aab", p = "c*a*b"
输出: false
解释: 'c*' 不能匹配 'aab' 的任何部分。

解题思路

该问题可以使用动态规划（Dynamic Programming）来解决。我们定义一个二维数组 dp[i][j]，其中 dp[i][j] 表示字符串 s 的前 i 个字符和模式 p 的前 j 个字符是否匹配。

1. 初始化 dp[0][0] = True，表示两个空字符串是匹配的。
2. 如果 p 的第 j 个字符是 *，则 dp[i][j] 可以由 dp[i][j-1] 或 dp[i-1][j]（且 s[i-1] == p[j-1] 或 p[j-1] 是 ?）推导出来。
3. 如果 p 的第 j 个字符不是 *，则 dp[i][j] 为真当且仅当 i > 0 且 (s[i-1] == p[j-1] 或 p[j-1] 是 ?)，并且 dp[i-1][j-1] 为真。

PHP 代码示例

function isMatch($s, $p) {
    $m = strlen($s);
    $n = strlen($p);
    
    $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, false));
    $dp[0][0] = true;

    for ($j = 1; $j <= $n; $j++) {
        if ($p[$j - 1] == '*') {
            $dp[0][$j] = $dp[0][$j - 1];
        }
    }

    for ($i = 1; $i <= $m; $i++) {
        for ($j = 1; $j <= $n; $j++) {
            if ($p[$j - 1] == '*') {
                $dp[$i][$j] = $dp[$i][$j - 1] || ($dp[$i - 1][$j] && ($s[$i - 1] == $p[$j - 2] || $p[$j - 2] == '?'));
            } elseif ($s[$i - 1] == $p[$j - 1] || $p[$j - 1] == '?') {
                $dp[$i][$j] = $dp[$i - 1][$j - 1];
            }
        }
    }

    return $dp[$m][$n];
}

Python 代码示例

def isMatch(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True

    for j in range(1, n + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 1]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                dp[i][j] = dp[i][j - 1] or (dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '?'))
            elif s[i - 1] == p[j - 1] or p[j - 1] == '?':
                dp[i][j] = dp[i - 1][j - 1]

    return dp[m][n]

JavaScript 代码示例

function isMatch(s, p) {
    const m = s.length;
    const n = p.length;
    const dp = Array.from({length: m + 1}, () => Array(n + 1).fill(false));
    dp[0][0] = true;

    for (let j = 1; j <= n; j++) {
        if (p[j - 1] === '*') {
            dp[0][j] = dp[0][j - 1];
        }
    }

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (p[j - 1] === '*') {
                dp[i][j] = dp[i][j - 1] || (dp[i - 1][j] && (s[i - 1] === p[j - 2] || p[j - 2] === '?'));
            } else if (s[i - 1] === p[j - 1] || p[j - 1] === '?') {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }

    return dp[m][n];
}

码小课网站中有更多相关内容分享给大家学习，包括但不限于算法、数据结构、面试技巧等，欢迎大家访问学习。