备考首页> 数据结构> 字符串
54

编程题 54 /86

请实现支持'?'and'*'.的通配符模式匹配
'?' 可以匹配任何单个字符。
'*' 可以匹配任何字符序列（包括空序列）。
返回两个字符串是否匹配
函数声明为：
bool isMatch(string s,string p)
下面给出一些样例：
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "d*a*b") → false
数据范围：字符串长度满足
进阶：空间复杂度 ，时间复杂度

参考答案

用双指针+贪心算法：
用is和ip表示星号在s和p中匹配的位置，初始值都为-1，i和j表示当前匹配的位置，匹配过程如下：
如果s和p中字符匹配，则分别自增 i 和 j ，否则如果p中当前字符为星号，则标记is和ip，同时自增j，否则如果is>=0，表示之前匹配过星号，因为星号可以匹配任意字符串，所以继续递增i，同时移动j为ip下一个字符，否则返回false，当s中字符匹配完，p中字符不能有除星号以外字符。
纠错 收藏
查看讨论
上一题 下一题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号