题解 | #通配符匹配#

通配符匹配

1、题意重述

请实现支持'?'and'*'的通配符模式匹配

'?' 可以匹配任何单个字符。

'*' 可以匹配任何字符序列（包括空序列）。

换句话说，就是使？能够等于任何一个字符，*能够等于任何一个字符序列。

2、思路整理

使用贪心的思想：

Step1:对于两个字符串，我们用i和j分别标记需要匹配的位置。如果i和j指向的字符匹配，则i++，j++。

Step2：当遇到''号时，因为''号可以匹配任何一个字符串，我们用i_Star和j_Star来标记星号匹配的开始位置，尽可能多的让'*'号匹配多的字符串，然后继续判断。

Step3：当发现字符不匹配且没有星号出现，但是i_Star > 0时，说明星号匹配的字数不对，此时根据i_Star记录的位置进行回溯。

Step4：重复上面过程，最终得到两个字符串是否匹配。

3、代码实现

bool isMatch(string s, string p) {
      int i = 0, j = 0, iStar = -1, jStar = -1, m = s.size(), n = p.size();
      while (i < m) {
          if (j < n && (s[i] == p[j] || p[j] == '?')) {
              ++i, ++j;//i，j向后瞬移
          } else if (j < n && p[j] == '*') {
              iStar = i;//记录星号
              jStar = j++;
          } else if (iStar >= 0) {
              i = ++iStar;
              j = jStar + 1;
              //j回溯到jstar+1 重新使用p串*后的部分开始对s串istar
          } else return false;
      }
      while (j < n && p[j] == '*') 
           ++j;//去除多余星号
      return j == n;
  }

4、复杂度分析

时间复杂度：一层循环，因此时间复杂度为$O(N)O(N)$。

空间复杂度：使用了常数级内存地址空间，因此空间复杂度为$O(1)O(1)$。