英文原文
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:
'?'Matches any single character.'*'Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Example 1:
Input: s = "aa", p = "a" Output: false Explanation: "a" does not match the entire string "aa".
Example 2:
Input: s = "aa", p = "*" Output: true Explanation: '*' matches any sequence.
Example 3:
Input: s = "cb", p = "?a" Output: false Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Example 4:
Input: s = "adceb", p = "*a*b" Output: true Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
Example 5:
Input: s = "acdcb", p = "a*c?b" Output: false
Constraints:
0 <= s.length, p.length <= 2000scontains only lowercase English letters.pcontains only lowercase English letters,'?'or'*'.
中文题目
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
'?' 可以匹配任何单个字符。 '*' 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。
说明:
s可能为空，且只包含从a-z的小写字母。p可能为空，且只包含从a-z的小写字母，以及字符?和*。
示例 1:
输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入: s = "aa" p = "*" 输出: true 解释: '*' 可以匹配任意字符串。
示例 3:
输入: s = "cb" p = "?a" 输出: false 解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
示例 4:
输入: s = "adceb" p = "*a*b" 输出: true 解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
示例 5:
输入: s = "acdcb" p = "a*c?b" 输出: false
通过代码
高赞题解
大嘎好，我又来画表了
我们来看这样一个表
其中，横轴为string s，纵轴为pattern p
这个表第(m,n)个格子的意义是:【p从0位置到m位置】这一整段，是否能与【s从0位置到n位置】这一整段匹配
也就是说，如果表格的下面这一个位置储存的是T(True)：
说明，”adcb”和”a*b”这一段是可以匹配的，你不用管前面发生了什么，你只要知道，这两段是匹配的，这就是动态规划为什么很棒棒
好，我们回到最初的起点。那么我们如何在这个表格上愉快地行走呢？
我在(START,START)这个位置放了一个T，这就是我们开始行走的位置
只有在T时才能继续往下走
那么从T可以往哪个方向走？
这道题是一个字符串匹配题，那字符串匹配肯定是不能回头的，你不可能在”abcde”里面倒着走，比如从e走到d
这个“不能倒着走”的规定，反映到我们的表格当中，就是只能往右下角走，大家可以细品一下为什么
(往右走、往下走也是有可能的，待会儿我们再说；反正左、上、左上角是不可能的，因为不能倒着走！)
往右下角走，我来举个例子，比如从刚才的初始位置出发，往右下角走一格，来到(a,a)这个位置，发现新引入的这两个字母正好匹配，于是我们在这里记录一个“T”。
就是这么简单，如果p和s里只有字母，没有”*“和”?”这两个东西，每次你只要从原来T的某个格子往右下角走一格，如果新引入的两个字母正好匹配，你就可以在新的格子里记录一个T。
再敲一次黑板：只能从T的格子走，如果某个格子里没有东西(即False)，你是不可以从那里出发的。
下面我们来介绍”*“和”?”
我为什么在标题里称这个表格为一个棋盘，是因为我觉得这像是一个下棋游戏
我们知道，中国象棋里每个棋子的功能都不同，像小兵每次只能直走一格，但车却可以直走任意格，还有的棋子则能跳着走
我们这里，普通字母如a、b就像是小兵角色，遇到他们只能右下走一格,走完这一步后判断新引入两个字母是否匹配才能记录T；
而”*”和”?”则是有特殊技能的角色！
(我到底在干嘛？)
角色：”*“
特技：铲平道路
描述：如果这一行是”*“，可以从上一行的任意T出发，向下、右铲平这一行的任意道路
示例：
所到之处，皆为平地
“*“可以从原来T向正下方走的原因：星号可以匹配空串
“*“可以铲平所有右边道路的原因：星号可以匹配任意长度字符串
大家可以品一品这两个原因。
在讲解另一个狠角色”?”之前，我们再往下走两步，巩固一下之前的知识。
接下来我们在pattern里遇到了一个b，它是一个普通字母，所以只能从上一行某个T往右下角走到达，而且字母匹配才能记录T，于是我们发现可以走这两步：
接下来，”?”隆重登场了
角色：”?”
特技：狸猫换太子
描述：如果这一行是”?”，从上一行某个T也只能向右下角走，但不必匹配字母就能记录T
示例：
只要有T就可以直接往右下角走一格，不用在意字母。这里太子“e”被狸猫”?”抵消了
wow，一下子来到了最后一格，小兵走一格就可以liao
要判定是否成功匹配，只要看一个格子！！如果最最右下角的格子是T，那就是匹配成功了，不用在意之前到底发生了什么
所以我们成功了，撒花✿✿ヽ(^▽^)ノ✿
举个例子，像这种情况(我把s的最后一个字母b换成了e)就是不成功了：
附Python代码
class Solution:
def isMatch(self, s: str, p: str) -> bool:
#s横，p纵
#土味拼音变量名
zong = len(p)+1 #纵轴长度
heng = len(s)+1 #横轴长度
table = [[False]*heng for i in range(zong)]
table[0][0] = True
if p.startswith("*"):
table[1] = [True]*heng
for m in range(1,zong):
path = False #是否可以在该行使用*的特技
for n in range(1,heng):
if p[m-1] == "*": #m是表格的索引，但不是p的索引
if table[m-1][0] == True:
table[m] = [True]*heng
if table[m-1][n]: #只要顶上有了True，就可以开通*接下来的所有道路
path = True
if path:
table[m][n] = True
elif p[m-1] == "?" or p[m-1]==s[n-1]: #先判断字母是否符合
table[m][n] = table[m-1][n-1] #再看左上方格子是不是T
return table[zong-1][heng-1]统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 89056 | 271318 | 32.8% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
相似题目
| 题目 | 难度 |
|---|---|
| 正则表达式匹配 | 困难 |
