44.通配符匹配

难度:困难

给定一个字符串(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

思路:
1.根据'*'拆分匹配规则
2.分段匹配,并确定匹配区间
3.确定是否完整匹配

相似提题型:
[Regular Expression Matching](leetcode.com)
相似题型解法:
[第八周ARTS总结](www.lanxingren.net)
展开
懒星人于2019-12-31 06:44发布的图片
懒星人于2019-12-31 06:44发布的图片
懒星人于2019-12-31 06:44发布的图片
评论