Skip to content

44. Wildcard Matching

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

  • '?' Matches any single character.
  • '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

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'.

Constraints:

  • 0 <= s.length, p.length <= 2000
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '?' or '*'.

Solution:

DFS:

class Solution {
    public boolean isMatch(String s, String p) {
        return dfs(0, 0, s, p);
    }

    private boolean dfs(int i, int j, String s, String p){
        // if pattern finished
        if (j == p.length()){
            if (i == s.length()){
                return true;
            }else{
                return false;
            }
        }


        // if s still has character and mattch current p or match ? 
        if (i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')){
            return dfs(i + 1, j + 1, s, p);
        }

        // if encounter '*'
        if (p.charAt(j) == '*'){
            // 1. * match "", dfs(i, j + 1, s, p) skip
            // 2. * match one or more than one pattern
            return dfs(i, j + 1, s, p) || (i < s.length() && dfs(i + 1, j, s, p));
            // 
        }

        return false;
    }
}

// TC: (2^n)
// SC: O(n)

DFS + Memo:

class Solution {
    public boolean isMatch(String s, String p) {
        Boolean[][] memo = new Boolean[s.length() + 1][p.length() + 1];
        return dfs(0, 0, s, p, memo);
    }

    private boolean dfs(int i, int j, String s, String p, Boolean[][] memo){
        // if pattern finished
        if (j == p.length()){
            if (i == s.length()){
                return true;
            }else{
                return false;
            }
        }

        if (memo[i][j] != null){
            return memo[i][j];
        }


        // if s still has character and mattch current p or match ? 
        if (i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')){
            return memo[i][j] = dfs(i + 1, j + 1, s, p, memo);
        }

        // if encounter '*'
        if (p.charAt(j) == '*'){
            // 1. * match "", dfs(i, j + 1, s, p) skip
            // 2. * match one or more than one pattern
            return memo[i][j] = dfs(i, j + 1, s, p, memo) || (i < s.length() && dfs(i + 1, j, s, p, memo));
            // 
        }

        return memo[i][j] = false;
    }
}

// TC: O(n*m)
// SC: O(n*m)

dfs(i, j+1)   // * 匹配空
dfs(i+1, j)   // * 匹配一个字符

https://arxiv.org/pdf/1407.0950