44. 通配符匹配
题目来源:力扣(LeetCode)https://leetcode-cn.com/problems/wildcard-matching
题目
给定一个字符串 (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
解题思路
思路:动态规划
这道题,跟 10. 正则表达式匹配 有点类似。关于【10. 正则表达式匹配 】的题解,可通过下面的链接进行阅读了解:
LeetCode 10. 正则表达式匹配 | Python
不过这里两题当中有点不一样的地方。【10. 正则表达式匹配 】此题的字符模式 p
的字符并不是单独的,例如:.*
两者关联会形成新的匹配模式。而本题中,p
的字符是独立的,并不会与前后产生关联。
先看题目说明,其中字符模式 p
,出现的情况有以下几种:
-
a-z
的小写字母,这里就仅对应相应的小写字母 -
?
,能够匹配任意单个字符(也即是任何一个字母) -
*
,匹配任意字符串(包括空字符串,也即是能够匹配 0 个或多个字符)
本题使用 动态规划 的解法,先定义状态,用 dp[i][j]
表示 s
的前 i 个字符串和模式 p
的前 j 个字符串是否匹配。那么进行状态转移的时候,会遇到下面的情况:
- 如果
p[j-1] == s[i-1]
或者p[j-1] == '?'
的时候,表示当前第 i 个字符是匹配的,那么dp[i][j]
可以由dp[i-1][j-1]
转换而来。 -
如果
p[j-1] == '*'
时,表示当前可以匹配 0 个字符或者多个字符。那么dp[i][j]
可以由dp[i][j-1]
或者dp[i-1][j]
转移而来。具体情况如下:- 当使用星号匹配时,
dp[i][j]
可以由dp[i-1][j]
转移而来 - 当不使用星号匹配时,
dp[i][j]
可以由dp[i][j-1]
转移而来
- 当使用星号匹配时,
所以,状态转移方程如下:
现在开始进行初始化,不过这里需要注意边界的问题:
- 初始化
dp[0][0]=True
,表示当字符串 s 和字符模式 p 都为空,表示能够匹配; -
dp[i][0]
表示字符模式 p 为空,无法匹配非空字符串,这里一定为 False;(初始 dp 为 False) -
dp[0][j]
这里表示字符模式 p 不为空,匹配空字符串。在这里,只有字符模式前 j 个字符都星号*
才能够成立,所以同样要单独分情况进行初始化。
具体的代码实现如下。
代码实现
class Solution:
def isMatch(self, s: str, p: str) -> bool:
s_length = len(s)
p_length = len(p)
# 初始化 dp
dp = [[False] * (p_length+1) for _ in range(s_length + 1)]
# 初始化 dp[0][0],表示空模式匹配空字符串
dp[0][0] = True
# 初始化 dp[0][j],非空模式匹配空字符串
for j in range(1, p_length+1):
if p[j-1] != "*":
break
dp[0][j] = True
for i in range(1, s_length+1):
for j in range(1, p_length+1):
# 代入转移方程
if p[j-1] == s[i-1] or p[j-1] == "?":
dp[i][j] = dp[i-1][j-1]
elif p[j-1] == "*":
dp[i][j] = dp[i-1][j] or dp[i][j-1]
return dp[s_length][p_length]
实现结果
文章原创,欢迎关注点赞。微信公众号《书所集录》同步更新,同样欢迎关注。