44. Wildcard Matching.md

44. Wildcard Matching

---

leetcode-cn Daily Challenge on July 5th, 2020.

---

Difficulty : Hard

---

Given an input string (s) and a pattern (p), 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).

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like ? or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Example 5:

Input:
s = "acdcb"
p = "a*c?b"
Output: false

---

Solution

same as 10. Regular Expression Matching.

• mine
  • Java

    • Recursion Time Limit Exceeded

      public boolean isMatch(String s, String p) {
          int m = s.length();
          int n = p.length();
          if(m == 0){
              return "*".equals(p) || n == 0;
          }
          if(n == 0){
              return false;
          }
          char[] arrS = s.toCharArray();
          char[] arrP = p.toCharArray();
          return check(arrS, arrP, 0, 0);
      }
      
      boolean check(char[] s, char[] p, int si, int pi){
          if(si == s.length){
              while(pi < p.length){
                  if(p[pi] != '*'){
                      return false;
                  }
                  pi++;
              }
              return true;
          }
          if(pi >= p.length){
              return false;
          }
          boolean match = s[si] == p[pi] || p[pi] == '?';
          if(p[pi] == '*'){
              return check(s, p, si, pi + 1) // * = ''
                  || check(s, p, si + 1, pi) // * = s[si] + s[si + 1] + ...
                  || check(s, p, si + 1, pi + 1); // * = s[si]
          } else {
              return match && check(s, p, si + 1, pi + 1);
          }
      }
      

    • DP - BottomUp Runtime: 24 ms, faster than 58.62%, Memory Usage: 46 MB, less than 8.11% of Java online submissions

      // O(m * n)time
      // O(m * n)space
      public boolean isMatch(String s, String p) {
          int m = s.length();
          int n = p.length();
          if (m == 0) {
              return "*".equals(p) || n == 0;
          }
          if (n == 0) {
              return false;
          }
          char[] arrS = s.toCharArray();
          char[] arrP = p.toCharArray();
          boolean[][] dp = new boolean[m + 1][n + 1];
          dp[0][0] = true;
          //when p is like "********sad?wq"
          for (int i = 1; i <= n; i++) {
              if (arrP[i - 1] == '*'){
                  dp[0][i] = true;
              }else {
                  break;
              }
          }
          for (int i = 1; i <= m; i++) {
              for (int j = 1; j <= n; j++) {
                  if (arrP[j - 1] == '*') {
                      // * = ''
                      // * = arrS[i]
                      dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                  } else if(arrS[i - 1] == arrP[j - 1] || arrP[j - 1] == '?'){
                      dp[i][j] = dp[i - 1][j - 1];
                  }
              }
          }
          return dp[m][n];
      }
      

---

• leetcode solution
  • Greedy Runtime: 3 ms, faster than 87.52%, Memory Usage: 41.2 MB, less than 28.13% of Java online submissions

    // O(lenS * lenP)time
    // O(1)space
    public boolean isMatch(String s, String p) {
        int sRight = s.length(), pRight = p.length();
        while (sRight > 0 && pRight > 0 && p.charAt(pRight - 1) != '*') {
            if (charMatch(s.charAt(sRight - 1), p.charAt(pRight - 1))) {
                --sRight;
                --pRight;
            } else {
                return false;
            }
        }
    
        if (pRight == 0) {
            return sRight == 0;
        }
    
        int sIndex = 0, pIndex = 0;
        int sRecord = -1, pRecord = -1;
        
        while (sIndex < sRight && pIndex < pRight) {
            if (p.charAt(pIndex) == '*') {
                ++pIndex;
                sRecord = sIndex;
                pRecord = pIndex;
            } else if (charMatch(s.charAt(sIndex), p.charAt(pIndex))) {
                ++sIndex;
                ++pIndex;
            } else if (sRecord != -1 && sRecord + 1 < sRight) {
                ++sRecord;
                sIndex = sRecord;
                pIndex = pRecord;
            } else {
                return false;
            }
        }
    
        return allStars(p, pIndex, pRight);
    }
    
    public boolean allStars(String str, int left, int right) {
        for (int i = left; i < right; ++i) {
            if (str.charAt(i) != '*') {
                return false;
            }
        }
        return true;
    }
    
    public boolean charMatch(char u, char v) {
        return u == v || v == '?';
    }
    

---