【leetcode】44 Wildcard Matching

发表于 | 分类于 ，

* ? 匹配


描述

给定输入字符串和模式（p），实现通配符模式匹配并支持’？’ 和’*’。

‘？’ 匹配任何单个字符。
‘*’匹配任何字符序列（包括空序列）。
匹配应覆盖整个输入字符串（不是部分）。

样例

样例1

1
2
输入: s = "adceb"  p = "*a*b"
输出: true

样例2

1
2
输入: s = "acdcb"  p = "a*c?b"
输出: false

思路

回溯，记录上一次*的位置，遇到错误则返回。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {

public:
    bool isMatch(string s, string p){
        int sIdxLast = -1, pIdxLast= -1;
        int sIdx=0,pIdx=0;
        while(sIdx != s.size()){
            //Skip this * 
            if(p[pIdx] == '*'){
                pIdx++;
                if(pIdx==p.size()){ return true;}
                // Store the index 
                // So we can back
                sIdxLast = sIdx;
                pIdxLast = pIdx;
            }
            else if(p[pIdx] == '?' || p[pIdx] == s[sIdx]){
                pIdx++;sIdx++;
            }
            else if(sIdxLast != -1){
                // back
                sIdx = ++sIdxLast;
                pIdx = pIdxLast;
            }
            else{
                return false;
            }
        }
        while(p[pIdx]== '*' ){pIdx++;}
        return pIdx == p.size();
    }
};

下面这份代码会超时
知道为什么吗？两份代码的回溯有什么区别？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isMatch(string s, string p){
         if (p.empty())    return s.empty();
         if (s.empty()){
             for(int i=0;i<p.size();i++){
                 if(p[i]!= '*') { return false;}
             }
             return true;
         }
         cout << p[0]<<endl;
          if(p[0] == '*'){
              return isMatch(s,p.substr(1)) ||  isMatch(s.substr(1),p);
          }
          else if(p[0] == '?' || p[0] == s[0]){
              return isMatch(s.substr(1),p.substr(1));
          }
         else  {
             return false;
         }

    }
};

第一份代码随着循环的进行，s的长度一直在减小，而第二份代码则会一直回溯，因为中止条件 s.empty() 和 p.empty() 都很难达到，或者说不是按照线性递减的。

参考

原题链接