44. Wildcard Matching.md

44. Wildcard Matching

Question:

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

二刷

1. 这道题在一刷的时候完全没AC。
2. 要通过DP解决这题。初始化，当s为空串时，只要p的字符等于*，那么dp[0][j] = dp[0][j - 1];
3. 解空间：
   • 当p等于s或p=？时，当前结果为上一位结果。dp[i][j] = dp[i - 1][j - 1];
   • 当p=时，dp[i][j] = dp[i - 1]j || dp[i][j - 1] (说明表示空)
   • 不满足上述条件则为false。

class Solution {
    public boolean isMatch(String s, String p) {
        if(s == null || p == null) return false;
        int sLen = s.length(), pLen = p.length();
        boolean[][] dp = new boolean[sLen + 1][pLen + 1];
        dp[0][0] = true;
        char[] sArr = s.toCharArray();
        char[] pArr = p.toCharArray();
        for(int i = 1; i <= pLen; i++)
            if(pArr[i - 1] == '*') dp[0][i] = dp[0][i - 1];
        for(int i = 1; i <= sLen; i++){
            char a = sArr[i - 1];
            for(int j = 1; j <= pLen; j++){
                char b = pArr[j - 1];
                if(match(a, b)) dp[i][j] = dp[i - 1][j - 1];
                else if(b == '*')
                    dp[i][j] =  dp[i - 1][j] || dp[i][j - 1];
                else dp[i][j] = false;
            }
        }
        return dp[sLen][pLen];
    }
    private boolean match(char a, char b){
        return a == b || b == '?';
    }
}

Third Time

• Method 1: dp

  class Solution {
      public boolean isMatch(String s, String p) {
          char[] sArr = s.toCharArray();
          char[] pArr = p.toCharArray();
          int sLen = sArr.length, pLen = pArr.length;
          boolean[][] dp = new boolean[sLen + 1][pLen + 1];
          dp[0][0] = true;
          for(int i = 1; i <= pLen; i++)
              if(pArr[i - 1] == '*')
                  dp[0][i] = dp[0][i - 1];
          for(int i = 1; i <= sLen; i++){
              for(int j = 1; j <= pLen; j++){
                  if(match(sArr[i - 1], pArr[j - 1])) dp[i][j] |= dp[i - 1][j - 1];
                  else if(pArr[j - 1] == '*'){
                      dp[i][j] |= dp[i - 1][j] || dp[i - 1][j - 1] || dp[i][j - 1];
                  }
              }
          }
          return dp[sLen][pLen];
      }
      private boolean match(char a, char b){
          return a == b || b == '?';
      }
  }