Wildcard Matching

Question

  1. Implement wildcard pattern matching with support for '?' and '*'.
  3. '?' Matches any single character.
  4. '*' Matches any sequence of characters (including the empty sequence).
  5. The matching should cover the entire input string (not partial).
  7. Example
  8. isMatch("aa","a") → false
  9. isMatch("aa","aa") → true
  10. isMatch("aaa","aa") → false
  11. isMatch("aa", "*") → true
  12. isMatch("aa", "a*") → true
  13. isMatch("ab", "?*") → true
  14. isMatch("aab", "c*a*b") → false

题解1 - DFS

字符串的通配实现。’?‘表示匹配单一字符，’*‘可匹配任意多字符串(包含零个)。要匹配的字符串设为s, 模式匹配用的字符串设为p，那么如果是普通字符，两个字符串索引向前推进一位即可，如果p中的字符是?也好办，同上处理，向前推进一位。所以现在的关键就在于如何处理’*‘, 因为*可匹配0, 1, 2…个字符，所以遇到*时，s应该尽可能的向前推进，注意到p中*后面可能跟有其他普通字符，故s向前推进多少位直接与p中*后面的字符相关。同时此时两个字符串的索引处即成为回溯点，如果后面的字符串匹配不成功，则s中的索引向前推进，向前推进的字符串即表示和p中*匹配的字符个数。

Java

  1. public class Solution {
  2.     /**
  3.      * @param s: A string
  4.      * @param p: A string includes "?" and "*"
  5.      * @return: A boolean
  6.      */
  7.     public boolean isMatch(String s, String p) {
  8.         if (s == null || p == null) return false;
  9.         if (s.length() == 0|| p.length() == 0) return false;
  11.         return helper(s, 0, p, 0);
  12.     }
  14.     private boolean helper(String s, int si, String p, int pj) {
  15.         // index out of range check
  16.         if (si == s.length() || pj == p.length()) {
  17.             if (si == s.length() && pj == p.length()) {
  18.                 return true;
  19.             } else {
  20.                 return false;
  21.             }
  22.         }
  24.         if (p.charAt(pj) == '*') {
  25.             // remove coninuous *
  26.             while (p.charAt(pj) == '*') {
  27.                 pj++;
  28.                 // index out of range check
  29.                 if (pj == p.length()) return true;
  30.             }
  32.             // compare remaining part of p after * with s
  33.             while (si < s.length() && !helper(s, si, p, pj)) {
  34.                 si++;
  35.             }
  36.             // substring of p equals to s
  37.             return si != s.length();
  38.         } else if (s.charAt(si) == p.charAt(pj) || p.charAt(pj) == '?') {
  39.             return helper(s, si + 1, p, pj + 1);
  40.         } else {
  41.             return false;
  42.         }
  43.     }
  44. }

源码分析

其中对*的处理和递归回溯是这段代码的精华。

复杂度分析

最坏情况下需要不断回溯，时间复杂度 O(n!) \times O(m!), 空间复杂度 O(1)(不含栈空间)。

题解2

C++

  1. bool isMatch(string s, string p) {
  2.     int star = 0, ss = 0, i = 0, j = 0;
  3.     while (s[i]) {
  4.         if (p[j] == '?' || p[j] == s[i]) {j++; i++; continue;}
  5.         if (p[j] == '*') {star = ++j; ss = i; continue;}
  6.         if (star) {j = star; i = ++ss; continue;}
  7.         return false;
  8.     }
  9.     while (p[j] == '*') j++;
  10.     return !p[j];
  11. }

Reference