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 == '?';
    }
}