Leetcode (44) Wildcard Matching

Leetcode (44) 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

• 题意：给定两个字符串，一个是普通字符串，一个是用于匹配的字符串，匹配的字符串中的’?’能够代替任何一个字母，’*’能够代替任何长度的字符串。求解，两个字符串能否配对。

• 思路：
  
  • 使用两个指针，sid对应于普通字符串，pid对应另一个字符串。两个都重头开始直接配对。
  • 对于’?’只需要直接配对接下来的一个字符即可。
  • 而对于’*’，首先直观的想法就是枚举它要配对多少个，然后递归求解即可。但是这样的方法过于暴力，复杂度高。
  • 实际上枚举它配对多少个的过程并不一定要暴力枚举，实际上要达到的效果就是使得*下一个字母能够配对，如”*a”对应于”cdefga”，目的只是要”*”代替”cdefg”，于是sid就要不停地往前移动，直到对应的时候。
  • 可是，这时候就有一种情况就是”*a”对应于”cdefgada”的时候，实际上”*”要代替”cdefgad”，因此仍然需要回溯，即假设a是匹配第一个a然后发现不行的时候，要能够回到之前刚匹配的时候（还原pid和sid），做到让’*’继续将a覆盖。
  • 进一步优化，有个贪心的地方就是当pid一路挪动，遇到一个’*’之后又遇到了第二个’*’，那么此时就可以将pid回溯的位置往前移，因为’*’可以代替任何长度的字符串，与其让前一个’*’覆盖地尽可能长，不如开始下一个’*’的匹配，减少了回溯的深度之余，实际上这是相同的，相当于剪枝。
  • 时间复杂度方面是 O(n2) $O(n^2)$，但这是一个非常松的上界，往往更靠近线性复杂度，空间复杂度则是 O(1) $O(1)$

class Solution {
public:bool isMatch(const string& s, const string& p) {int si=0, pi=0;int slast, plast=-1;int slen=s.length(), plen=p.length();while (si < slen){if (s[si] == p[pi] || p[pi] == '?'){si++;pi++;}else if (pi < plen && p[pi] == '*')  // 贪心{slast=si;while (pi < plen && p[pi] == '*'){pi++;}plast=pi;}else if (plast >= 0)   // 有回溯位置，则回溯{si=slast+1;slast++;pi=plast;}else{return false;}}while (pi < plen && p[pi] == '*') pi++;return pi==plen;}
};