Wildcard Matching 外卡匹配

Wildcard Matching 外卡匹配

题目描述

Implement wildcard pattern matching with support for'?'and'*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).The matching should cover the entire input string (not partial).The function prototype should be:
bool isMatch(const char *s, const char *p)Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

双指针法

复杂度

时间 O(N) 空间 O(1)

思路

假设我们用两个指针分别指向s和p字符串中要匹配的位置，首先分析下通配符匹配过程中会有哪些情况是成功：

1. s的字符和p的字符相等

2. p中的字符是?，这时无论s的字符是什么都可以匹配一个

3. p中遇到了一个*，这时无论s的字符是什么都没关系

4. 之前的都不符合，但是p在之前的位置有一个*，我们可以从上一个*后面开始匹配 （例：s=ab,p=?*c，此时我们就要用b之后的字符去匹配c）

5. s已经匹配完，但是p后面还有很多连续的`*.

具体算法如下：

- 定义scur, pcur, sstar, pstar

- 如果*scur存在

  - 如果*scur等于*pcur或者*pcur为 '?'，则scur和pcur都自增1

  - 如果*pcur为'*'，则pstar指向pcur位置，pcur自增1，且sstar指向scur

  - 如果pstar存在，则pcur指向pstar的下一个位置，scur指向sstar自增1后的位置

- 如果pcur为'*'，则pcur自增1

- 若*pcur存在，返回False，若不存在，返回True

实现代码：

             class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        const char *scur = s, *pcur = p, *sstar = NULL, *pstar = NULL;
    while (*scur) 
    {
        if (*scur == *pcur || *pcur == '?') 
        {
            ++scur;
            ++pcur;
        } 
        else 
            if (*pcur == '*')
        {
            pstar = pcur++;
            sstar = scur;
        } 
        else 
            if (pstar) 
        {
            pcur = pstar + 1;
            scur = ++sstar;
        } 
        else 
            return false;
    } 
    while (*pcur == '*') ++pcur; //如果s与p比较结束，p还有剩余的，一直遍历结束；
    return !*pcur;  //剩下的只能全为'*'；
    }
};