Hard

题目描述

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

  • '?' 可以匹配任何单个字符。
  • '*' 可以匹配任意字符序列（包括空序列）。

所给定的匹配应该覆盖整个字符串 s（不是部分字符串）。

示例 1：

输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例 2：

输入：s = "aa", p = "*"
输出：true
解释：'*' 可以匹配任意字符序列。

示例 3：

输入：s = "cb", p = "?a"
输出：false
解释：'?' 可以匹配 'c', 但第二个字符是 'a'，无法匹配 'b'。

提示：

  • 0 <= s.length, p.length <= 2000
  • s 仅由小写英文字母组成
  • p 仅由小写英文字母、'?' 或 '*' 组成

解题思路

解题思路

这道题有两种主要解法：动态规划和双指针贪心。

方法一：动态规划（推荐）

定义状态：dp[i][j] 表示字符串 s 的前 i 个字符是否能够被模式 p 的前 j 个字符匹配。

状态转移：

  1. 如果 p[j-1] == '*'：
    • 不使用 '*'：dp[i][j] = dp[i][j-1]
    • 使用 '*' 匹配一个或多个字符：dp[i][j] = dp[i-1][j]
  2. 如果 p[j-1] == '?' 或 p[j-1] == s[i-1]：
    • dp[i][j] = dp[i-1][j-1]
  3. 否则：dp[i][j] = false

方法二：双指针贪心

使用四个指针：sIndex、pIndex、starIdx、match。遇到 '*' 时记录位置，如果后续匹配失败则回到 '*' 位置重新尝试。

动态规划方法更直观易懂，时间复杂度稳定，是首选方法。双指针方法空间复杂度更优，但实现相对复杂。

代码实现

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        
        dp[0][0] = true;
        
        // 处理模式串开头的连续 '*'
        for (int j = 1; j <= n; j++) {
            if (p[j - 1] == '*') {
                dp[0][j] = dp[0][j - 1];
            }
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                } else if (p[j - 1] == '?' || p[j - 1] == s[i - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        
        return dp[m][n];
    }
};

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        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 - 1][j] or dp[i][j - 1]
                elif p[j - 1] == '?' or p[j - 1] == s[i - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
        
        return dp[m][n]

public class Solution {
    public bool IsMatch(string s, string p) {
        int m = s.Length, n = p.Length;
        bool[,] dp = new bool[m + 1, n + 1];
        
        dp[0, 0] = true;
        
        // 处理模式串开头的连续 '*'
        for (int j = 1; j <= n; j++) {
            if (p[j - 1] == '*') {
                dp[0, j] = dp[0, j - 1];
            }
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == '*') {
                    dp[i, j] = dp[i - 1, j] || dp[i, j - 1];
                } else if (p[j - 1] == '?' || p[j - 1] == s[i - 1]) {
                    dp[i, j] = dp[i - 1, j - 1];
                }
            }
        }
        
        return dp[m, n];
    }
}

var isMatch = function(s, p) {
    const m = s.length, n = p.length;
    const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(false));
    
    dp[0][0] = true;
    
    // 处理模式串开头的连续 '*'
    for (let j = 1; j <= n; j++) {
        if (p[j - 1]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
动态规划O(m × n)O(m × n)
双指针贪心O(m × n)O(1)

其中 m 为字符串 s 的长度，n 为模式串 p 的长度。动态规划方法在最坏情况下仍保持稳定的时间复杂度，而双指针方法虽然平均情况较优，但最坏情况下可能退化。

相关题目