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:

  1. bool isMatch(const char *s, const char *p)

Some examples:

  1. isMatch("aa","a") → false
  2. isMatch("aa","aa") → true
  3. isMatch("aaa","aa") → false
  4. isMatch("aa", "*") → true
  5. isMatch("aa", "a*") → true
  6. isMatch("ab", "?*") → true
  7. isMatch("aab", "c*a*b") → false

分析

跟上一题很类似。

主要是''的匹配问题。p每遇到一个''，就保留住当前'*'的坐标和s的坐标，然后s从前往后扫描，如果不成功，则s++，重新扫描。

递归版

  1. // Wildcard Matching
  2. // 递归版，会超时，用于帮助理解题意
  3. // 时间复杂度O(n!*m!)，空间复杂度O(n)
  4. class Solution {
  5. public:
  6.     bool isMatch(const string& s, const string& p) {
  7.         return isMatch(s.c_str(), p.c_str());
  8.     }
  9. private:
  10.     bool isMatch(const char *s, const char *p) {
  11.         if (*p == '\0' || *s == '\0') return *p == *s;
  12.         else if (*p == '*') {
  13.             while (*p == '*') ++p;  //skip continuous '*'
  14.             if (*p == '\0') return true;
  15.             while (*s != '\0' && !isMatch(s, p)) ++s;
  17.             return *s != '\0';
  18.         }
  19.         else if (*p == *s || *p == '?') return isMatch(++s, ++p);
  20.         else return false;
  21.     }
  22. };

迭代版

  1. // Wildcard Matching
  2. // 迭代版，时间复杂度O(n*m)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     bool isMatch(const string& s, const string& p) {
  6.         return isMatch(s.c_str(), p.c_str());
  7.     }
  8. private:
  9.     bool isMatch(const char *s, const char *p) {
  10.         bool star = false;
  11.         const char *str, *ptr;
  12.         for (str = s, ptr = p; *str != '\0'; str++, ptr++) {
  13.             switch (*ptr) {
  14.             case '?':
  15.                 break;
  16.             case '*':
  17.                 star = true;
  18.                 s = str, p = ptr;
  19.                 while (*p == '*') p++;  //skip continuous '*'
  20.                 if (*p == '\0') return true;
  21.                 str = s - 1;
  22.                 ptr = p - 1;
  23.                 break;
  24.             default:
  25.                 if (*str != *ptr) {
  26.                     // 如果前面没有'*'，则匹配不成功
  27.                     if (!star) return false;
  28.                     s++;
  29.                     str = s - 1;
  30.                     ptr = p - 1;
  31.                 }
  32.             }
  33.         }
  34.         while (*ptr == '*') ptr++;
  35.         return (*ptr == '\0');
  36.     }
  37. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/string/wildcard-matching.html