What is the main pattern used in Wildcard Matching?

Wildcard Matching primarily uses state transition dynamic programming to track all possible matches between the input string and pattern efficiently.

How does '*' affect matching in this problem?

The '*' character matches zero or more characters, requiring careful tracking of previous match positions to ensure correct backtracking and coverage.

Can '?' match multiple characters?

No, '?' matches exactly one character; the DP or greedy approach must account for single-character consumption and proper index advancement.

What are typical edge cases to test?

Edge cases include empty strings, patterns starting or ending with '*', consecutive '*' characters, and strings longer than the pattern to ensure full coverage matching.

Which approach is most efficient for large inputs?

The greedy two-pointer method often reduces time and space overhead compared to full DP while maintaining correctness, especially with long strings and patterns containing '*'.

#44

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

通配符匹配

给你一个输入字符串 ( s ) 和一个字符模式 ( p ) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配： '?' 可以匹配任何单个字符。 '*' 可以匹配任意字符序列（包括空字符序列）。判定匹配成功的充要条件是：字符模式必须能够完全匹配输入字符串（而不是部分匹配）。示例 1…

字符串动态规划贪心递归

题目描述

给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：

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

判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

示例 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 仅由小写英文字母、'?' 或 '*' 组成

lightbulb

解题思路

方法一：记忆化搜索

我们设计一个函数 $dfs(i, j)$ ，表示从字符串 $s$ 的第 $i$ 个字符开始和字符串 $p$ 的第 $j$ 个字符开始是否匹配。那么答案就是 $dfs(0, 0)$ 。

函数 $dfs(i, j)$ 的执行过程如下：

如果 $i \geq \textit{len}(s)$ ，那么只有当 $j \geq \textit{len}(p)$ 或者 $p[j] = '*'$ 且 $dfs(i, j + 1)$ 为真时， $dfs(i, j)$ 才为真。
如果 $j \geq \textit{len}(p)$ ，那么 $dfs(i, j)$ 为假。
如果 $p[j] = '*'$ ，那么 $dfs(i, j)$ 为真当且仅当 $dfs(i + 1, j)$ 或 $dfs(i + 1, j + 1)$ 或 $dfs(i, j + 1)$ 中有一个为真。
否则 $dfs(i, j)$ 为真当且仅当 $p[j] = '?'$ 或 $s[i] = p[j]$ 且 $dfs(i + 1, j + 1)$ 为真。

为了避免重复计算，我们使用记忆化搜索的方法，将 $dfs(i, j)$ 的结果存储在一个哈希表中。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是字符串 $s$ 和 $p$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        @cache
        def dfs(i: int, j: int) -> bool:
            if i >= len(s):
                return j >= len(p) or (p[j] == "*" and dfs(i, j + 1))
            if j >= len(p):
                return False
            if p[j] == "*":
                return dfs(i + 1, j) or dfs(i + 1, j + 1) or dfs(i, j + 1)
            return (p[j] == "?" or s[i] == p[j]) and dfs(i + 1, j + 1)

        return dfs(0, 0)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you correctly handle '*' matching multiple characters without skipping necessary DP states?
question_mark
Can you optimize space usage while maintaining full string coverage matching?
question_mark
Will you explain how consecutive '?' and '*' affect your state transitions and edge cases?

warning

常见陷阱

外企场景

error
Failing to initialize the DP table for empty strings or patterns with leading '*' characters.
error
Mismanaging backtracking when '*' is involved, causing incorrect false negatives.
error
Overlooking the need to match the entire string, allowing partial matches to incorrectly return true.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Matching with additional character classes like [a-z] or numeric ranges in the pattern.
arrow_right_alt
Wildcard Matching II: pattern allows escape characters and nested wildcards requiring modified DP transitions.
arrow_right_alt
Minimum edits required to transform string s to match pattern p considering '?' and '*' insertions.

help

常见问题

外企场景

继续练习

#241 为运算表达式设计优先级 #678 有效的括号字符串 #45 跳跃游戏 II