首页 > 试题广场 >

通配符匹配

[编程题]通配符匹配
  • 热度指数:27361 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
请实现支持'?'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
数据范围:字符串长度满足
进阶:空间复杂度 ,时间复杂度
示例1

输入

"ab","?*"

输出

true
示例2

输入

"ab","*"

输出

true
function isMatch(s, p) {     // s 的指针,p 的指针,s 的新起始位置, p 最新出现 '*' 的位置     let sIndex = 0, pIndex = 0, sStart = 0, star = null;     while (s[sIndex]) {         // 当 p 读到 '?' 或 p 当前字符与 s 匹配时,s 和 p 的指针同时后移一位         if (p[pIndex] === '?' || p[pIndex] === s[sIndex]) sIndex++, pIndex++;         // 当 p 读到 '*' 时,记录当前 s 的位置为新的起始位置,记录 '*' 的新位置,p的指针后移一位         else if (p[pIndex] === '*') sStart = sIndex, star = pIndex++;         // 当 p 出现过 '*' 且 p 当前位置的字符与 s 当前位置的字符不匹配时,s 的起始位置和 s 的指针同时后移一位,p 的指针重新从 '*' 的后一位开始         else if (star !== null) sIndex = ++sStart, pIndex = star + 1;         // 如果既没出现过 '?' 或 '*',也没有匹配的字符,直接返回 false         else return false;     }     // 跳过后面的所有 '*'     while (p[pIndex] === '*') pIndex++;     // 如果 p 的指针在 p 的末尾,说明模式匹配正确     return pIndex === p.length; }

编辑于 2021-04-20 16:05:18 回复(0)