Skip to content

44. Wildcard Matching

DifficultyHard

Description

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

Solutions

Thinking

The first idea is recurse character by character: literals and ? match one, * eats empty or more. Correct, but without memo the * branches explode. \(|s|, |p| \le 2000\) will time out.

The bottleneck is asking the same suffix pair \((i, j)\) over and over. The state is only “does \(s[i:]\) match \(p[j:]\)”; subproblems overlap heavily.

Cache \(dfs(i, j)\). The three * moves (consume one, advance both, skip *) are transitions on that state. Memoization turns exponential search into \(O(mn)\).

We design a function \(dfs(i, j)\), which represents whether the string \(s\) starting from the \(i\)-th character matches the string \(p\) starting from the \(j\)-th character. The answer is \(dfs(0, 0)\).

The execution process of the function \(dfs(i, j)\) is as follows:

  • If \(i \geq \textit{len}(s)\), then \(dfs(i, j)\) is true only when \(j \geq \textit{len}(p)\) or \(p[j] = '*'\) and \(dfs(i, j + 1)\) is true.
  • If \(j \geq \textit{len}(p)\), then \(dfs(i, j)\) is false.
  • If \(p[j] = '*'\), then \(dfs(i, j)\) is true if and only if \(dfs(i + 1, j)\) or \(dfs(i + 1, j + 1)\) or \(dfs(i, j + 1)\) is true.
  • Otherwise, \(dfs(i, j)\) is true if and only if \(p[j] = '?'\) or \(s[i] = p[j]\) and \(dfs(i + 1, j + 1)\) is true.

To avoid repeated calculations, we use the method of memoization search and store the result of \(dfs(i, j)\) in a hash table.

The time complexity is \(O(m \times n)\), and the space complexity is \(O(m \times n)\). Where \(m\) and \(n\) are the lengths of the strings \(s\) and \(p\), respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        @cache
        def dfs(i: int, j: int) -> bool:
            if i >= len(s):
                return j >= len(p) or (p[j] == "*" and dfs(i, j + 1))
            if j >= len(p):
                return False
            if p[j] == "*":
                return dfs(i + 1, j) or dfs(i + 1, j + 1) or dfs(i, j + 1)
            return (p[j] == "?" or s[i] == p[j]) and dfs(i + 1, j + 1)

        return dfs(0, 0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    private Boolean[][] f;
    private char[] s;
    private char[] p;
    private int m;
    private int n;

    public boolean isMatch(String s, String p) {
        this.s = s.toCharArray();
        this.p = p.toCharArray();
        m = s.length();
        n = p.length();
        f = new Boolean[m][n];
        return dfs(0, 0);
    }

    private boolean dfs(int i, int j) {
        if (i >= m) {
            return j >= n || (p[j] == '*' && dfs(i, j + 1));
        }
        if (j >= n) {
            return false;
        }
        if (f[i][j] != null) {
            return f[i][j];
        }
        if (p[j] == '*') {
            f[i][j] = dfs(i + 1, j) || dfs(i + 1, j + 1) || dfs(i, j + 1);
        } else {
            f[i][j] = (p[j] == '?' || s[i] == p[j]) && dfs(i + 1, j + 1);
        }
        return f[i][j];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<int>> f(m + 1, vector<int>(n + 1, -1));
        function<bool(int, int)> dfs = [&](int i, int j) {
            if (i >= m) {
                return j >= n || (p[j] == '*' && dfs(i, j + 1));
            }
            if (j >= n) {
                return false;
            }
            if (f[i][j] != -1) {
                return f[i][j] == 1;
            }
            if (p[j] == '*') {
                f[i][j] = dfs(i + 1, j) || dfs(i, j + 1) ? 1 : 0;
            } else {
                f[i][j] = (p[j] == '?' || s[i] == p[j]) && dfs(i + 1, j + 1) ? 1 : 0;
            }
            return f[i][j] == 1;
        };
        return dfs(0, 0);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func isMatch(s string, p string) bool {
    m, n := len(s), len(p)
    f := make([][]int, m+1)
    for i := range f {
        f[i] = make([]int, n+1)
    }
    var dfs func(i, j int) bool
    dfs = func(i, j int) bool {
        if i >= m {
            return j >= n || p[j] == '*' && dfs(i, j+1)
        }
        if j >= n {
            return false
        }
        if f[i][j] != 0 {
            return f[i][j] == 1
        }
        f[i][j] = 2
        ok := false
        if p[j] == '*' {
            ok = dfs(i+1, j) || dfs(i+1, j+1) || dfs(i, j+1)
        } else {
            ok = (p[j] == '?' || s[i] == p[j]) && dfs(i+1, j+1)
        }
        if ok {
            f[i][j] = 1
        }
        return ok
    }
    return dfs(0, 0)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function isMatch(s: string, p: string): boolean {
    const m = s.length;
    const n = p.length;
    const f: number[][] = Array.from({ length: m + 1 }, () =>
        Array.from({ length: n + 1 }, () => -1),
    );
    const dfs = (i: number, j: number): boolean => {
        if (i >= m) {
            return j >= n || (p[j] === '*' && dfs(i, j + 1));
        }
        if (j >= n) {
            return false;
        }
        if (f[i][j] !== -1) {
            return f[i][j] === 1;
        }
        if (p[j] === '*') {
            f[i][j] = dfs(i + 1, j) || dfs(i, j + 1) ? 1 : 0;
        } else {
            f[i][j] = (p[j] === '?' || s[i] === p[j]) && dfs(i + 1, j + 1) ? 1 : 0;
        }
        return f[i][j] === 1;
    };
    return dfs(0, 0);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Solution {
    private bool?[,] f;
    private char[] s;
    private char[] p;
    private int m;
    private int n;

    public bool IsMatch(string s, string p) {
        this.s = s.ToCharArray();
        this.p = p.ToCharArray();
        m = s.Length;
        n = p.Length;
        f = new bool?[m, n];
        return Dfs(0, 0);
    }

    private bool Dfs(int i, int j) {
        if (i >= m) {
            return j >= n || (p[j] == '*' && Dfs(i, j + 1));
        }
        if (j >= n) {
            return false;
        }
        if (f[i, j] != null) {
            return f[i, j].Value;
        }
        if (p[j] == '*') {
            f[i, j] = Dfs(i + 1, j) || Dfs(i + 1, j + 1) || Dfs(i, j + 1);
        } else {
            f[i, j] = (p[j] == '?' || s[i] == p[j]) && Dfs(i + 1, j + 1);
        }
        return f[i, j].Value;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    /**
     * @param string $s
     * @param string $p
     * @return boolean
     */
    private $f;
    private $s;
    private $p;
    private $m;
    private $n;

    function isMatch($s, $p) {
        $this->s = $s;
        $this->p = $p;
        $this->m = strlen($s);
        $this->n = strlen($p);
        $this->f = [];
        for ($i = 0; $i < $this->m; $i++) {
            $this->f[$i] = array_fill(0, $this->n, null);
        }
        return $this->dfs(0, 0);
    }

    function dfs($i, $j) {
        if ($i >= $this->m) {
            return $j >= $this->n || ($this->p[$j] == '*' && $this->dfs($i, $j + 1));
        }
        if ($j >= $this->n) {
            return false;
        }
        if ($this->f[$i][$j] !== null) {
            return $this->f[$i][$j];
        }
        if ($this->p[$j] == '*') {
            $this->f[$i][$j] =
                $this->dfs($i + 1, $j) || $this->dfs($i + 1, $j + 1) || $this->dfs($i, $j + 1);
        } else {
            $this->f[$i][$j] =
                ($this->p[$j] == '?' || $this->s[$i] == $this->p[$j]) && $this->dfs($i + 1, $j + 1);
        }
        return $this->f[$i][$j];
    }
}

Solution 2: Dynamic Programming

Thinking

Solution 1 already fills this match table from shorter prefixes to longer ones. The \(f[i][j]\) below is that same table.

Solution 1 already fills this table from shorter prefixes to longer ones.

Define \(f[i][j]\) to represent whether the first \(i\) characters of string \(s\) match the first \(j\) characters of string \(p\). Initially, \(f[0][0] = \textit{true}\), indicating that two empty strings are matching. For \(j \in [1, n]\), if \(p[j-1] = '*'\), then \(f[0][j] = f[0][j-1]\).

Next, we consider the case of \(i \in [1, m]\) and \(j \in [1, n]\):

  • If \(p[j-1] = '*'\), then \(f[i][j] = f[i-1][j] \lor f[i][j-1] \lor f[i-1][j-1]\).
  • Otherwise, \(f[i][j] = (p[j-1] = '?' \lor s[i-1] = p[j-1]) \land f[i-1][j-1]\).

The final answer is \(f[m][n]\).

The time complexity is \(O(m \times n)\), and the space complexity is \(O(m \times n)\). Where \(m\) and \(n\) are the lengths of the strings \(s\) and \(p\), respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        f = [[False] * (n + 1) for _ in range(m + 1)]
        f[0][0] = True
        for j in range(1, n + 1):
            if p[j - 1] == "*":
                f[0][j] = f[0][j - 1]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == "*":
                    f[i][j] = f[i - 1][j] or f[i][j - 1] or f[i - 1][j - 1]
                else:
                    f[i][j] = f[i - 1][j - 1] and (
                        p[j - 1] == "?" or s[i - 1] == p[j - 1]
                    )
        return f[m][n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int j = 1; j <= n; ++j) {
            if (p.charAt(j - 1) == '*') {
                f[0][j] = f[0][j - 1];
            }
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i - 1][j] || f[i][j - 1] || f[i - 1][j - 1];
                } else {
                    f[i][j] = f[i - 1][j - 1]
                        && (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1));
                }
            }
        }
        return f[m][n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        vector<vector<bool>> f(m + 1, vector<bool>(n + 1, false));
        f[0][0] = true;
        for (int j = 1; j <= n; ++j) {
            if (p[j - 1] == '*') {
                f[0][j] = f[0][j - 1];
            }
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    f[i][j] = f[i - 1][j] || f[i][j - 1] || f[i - 1][j - 1];
                } else {
                    f[i][j] = f[i - 1][j - 1] && (p[j - 1] == '?' || s[i - 1] == p[j - 1]);
                }
            }
        }
        return f[m][n];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func isMatch(s string, p string) bool {
    m, n := len(s), len(p)
    f := make([][]bool, m+1)
    for i := range f {
        f[i] = make([]bool, n+1)
    }
    f[0][0] = true
    for j := 1; j <= n; j++ {
        if p[j-1] == '*' {
            f[0][j] = f[0][j-1]
        }
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if p[j-1] == '*' {
                f[i][j] = f[i-1][j] || f[i][j-1] || f[i-1][j-1]
            } else {
                f[i][j] = f[i-1][j-1] && (p[j-1] == '?' || s[i-1] == p[j-1])
            }
        }
    }
    return f[m][n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function isMatch(s: string, p: string): boolean {
    const m: number = s.length;
    const n: number = p.length;
    const f: boolean[][] = Array.from({ length: m + 1 }, () =>
        Array.from({ length: n + 1 }, () => false),
    );
    f[0][0] = true;
    for (let j = 1; j <= n; ++j) {
        if (p.charAt(j - 1) === '*') {
            f[0][j] = f[0][j - 1];
        }
    }
    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            if (p[j - 1] === '*') {
                f[i][j] = f[i - 1][j] || f[i][j - 1] || f[i - 1][j - 1];
            } else {
                f[i][j] = f[i - 1][j - 1] && (p[j - 1] === '?' || s[i - 1] === p[j - 1]);
            }
        }
    }
    return f[m][n];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    /**
     * @param string $s
     * @param string $p
     * @return boolean
     */

    function isMatch($s, $p) {
        $m = strlen($s);
        $n = strlen($p);
        $f = [];
        for ($i = 0; $i <= $m; $i++) {
            $f[$i] = array_fill(0, $n + 1, false);
        }
        $f[0][0] = true;
        for ($j = 1; $j <= $n; $j++) {
            if ($p[$j - 1] == '*') {
                $f[0][$j] = $f[0][$j - 1];
            }
        }
        for ($i = 1; $i <= $m; $i++) {
            for ($j = 1; $j <= $n; $j++) {
                if ($p[$j - 1] == '*') {
                    $f[$i][$j] = $f[$i - 1][$j] || $f[$i][$j - 1] || $f[$i - 1][$j - 1];
                } else {
                    $f[$i][$j] =
                        $f[$i - 1][$j - 1] && ($p[$j - 1] == '?' || $s[$i - 1] == $p[$j - 1]);
                }
            }
        }
        return $f[$m][$n];
    }
}

Solution 3: Dynamic Programming

Thinking

Matching one character at a time is the natural first idea: a literal or ? consumes one character, and * consumes the empty string or any run. Both strings can have length \(2000\), and the first move on * is always \(dfs(i+1, j)\), so that chain is as deep as \(|s|\) and exceeds the default recursion limit.

The same index pair is asked repeatedly, and whether two prefixes match depends only on shorter prefixes.

Let \(f[i][j]\) mean the first \(i\) characters of \(s\) match the first \(j\) characters of \(p\). The empty pair is true, and a run of * on the pattern inherits along \(j\). Filling \(i\) and \(j\) from small to large works because a * reads the cell above, the cell to the left, and the diagonal, while a literal or ? reads only the diagonal.

Define \(f[i][j]\) to represent whether the first \(i\) characters of string \(s\) match the first \(j\) characters of string \(p\). Initially, \(f[0][0] = \textit{true}\), indicating that two empty strings are matching. For \(j \in [1, n]\), if \(p[j-1] = '*'\), then \(f[0][j] = f[0][j-1]\).

Next, we consider the case of \(i \in [1, m]\) and \(j \in [1, n]\):

  • If \(p[j-1] = '*'\), then \(f[i][j] = f[i-1][j] \lor f[i][j-1] \lor f[i-1][j-1]\).
  • Otherwise, \(f[i][j] = (p[j-1] = '?' \lor s[i-1] = p[j-1]) \land f[i-1][j-1]\).

The final answer is \(f[m][n]\).

The time complexity is \(O(m \times n)\), and the space complexity is \(O(m \times n)\). Where \(m\) and \(n\) are the lengths of the strings \(s\) and \(p\), respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        f = [[False] * (n + 1) for _ in range(m + 1)]
        f[0][0] = True
        for j in range(1, n + 1):
            if p[j - 1] == "*":
                f[0][j] = f[0][j - 1]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == "*":
                    f[i][j] = f[i - 1][j] or f[i][j - 1] or f[i - 1][j - 1]
                else:
                    f[i][j] = f[i - 1][j - 1] and (
                        p[j - 1] == "?" or s[i - 1] == p[j - 1]
                    )
        return f[m][n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int j = 1; j <= n; ++j) {
            if (p.charAt(j - 1) == '*') {
                f[0][j] = f[0][j - 1];
            }
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i - 1][j] || f[i][j - 1] || f[i - 1][j - 1];
                } else {
                    f[i][j] = f[i - 1][j - 1]
                        && (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1));
                }
            }
        }
        return f[m][n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        bool f[m + 1][n + 1];
        memset(f, false, sizeof(f));
        f[0][0] = true;
        for (int j = 1; j <= n; ++j) {
            if (p[j - 1] == '*') {
                f[0][j] = f[0][j - 1];
            }
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    f[i][j] = f[i - 1][j] || f[i][j - 1] || f[i - 1][j - 1];
                } else {
                    f[i][j] = f[i - 1][j - 1] && (p[j - 1] == '?' || s[i - 1] == p[j - 1]);
                }
            }
        }
        return f[m][n];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func isMatch(s string, p string) bool {
    m, n := len(s), len(p)
    f := make([][]bool, m+1)
    for i := range f {
        f[i] = make([]bool, n+1)
    }
    f[0][0] = true
    for j := 1; j <= n; j++ {
        if p[j-1] == '*' {
            f[0][j] = f[0][j-1]
        }
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if p[j-1] == '*' {
                f[i][j] = f[i-1][j] || f[i][j-1] || f[i-1][j-1]
            } else {
                f[i][j] = f[i-1][j-1] && (p[j-1] == '?' || s[i-1] == p[j-1])
            }
        }
    }
    return f[m][n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function isMatch(s: string, p: string): boolean {
    const m: number = s.length;
    const n: number = p.length;
    const f: boolean[][] = Array.from({ length: m + 1 }, () =>
        Array.from({ length: n + 1 }, () => false),
    );
    f[0][0] = true;
    for (let j = 1; j <= n; ++j) {
        if (p.charAt(j - 1) === '*') {
            f[0][j] = f[0][j - 1];
        }
    }
    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            if (p[j - 1] === '*') {
                f[i][j] = f[i - 1][j] || f[i][j - 1] || f[i - 1][j - 1];
            } else {
                f[i][j] = f[i - 1][j - 1] && (p[j - 1] === '?' || s[i - 1] === p[j - 1]);
            }
        }
    }
    return f[m][n];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public bool IsMatch(string s, string p) {
        int m = s.Length, n = p.Length;
        bool[,] f = new bool[m + 1, n + 1];
        f[0, 0] = true;
        for (int j = 1; j <= n; ++j) {
            if (p[j - 1] == '*') {
                f[0, j] = f[0, j - 1];
            }
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    f[i, j] = f[i - 1, j] || f[i, j - 1] || f[i - 1, j - 1];
                } else {
                    f[i, j] = f[i - 1, j - 1] && (p[j - 1] == '?' || s[i - 1] == p[j - 1]);
                }
            }
        }
        return f[m, n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    /**
     * @param string $s
     * @param string $p
     * @return boolean
     */

    function isMatch($s, $p) {
        $m = strlen($s);
        $n = strlen($p);
        $f = [];
        for ($i = 0; $i <= $m; $i++) {
            $f[$i] = array_fill(0, $n + 1, false);
        }
        $f[0][0] = true;
        for ($j = 1; $j <= $n; $j++) {
            if ($p[$j - 1] == '*') {
                $f[0][$j] = $f[0][$j - 1];
            }
        }
        for ($i = 1; $i <= $m; $i++) {
            for ($j = 1; $j <= $n; $j++) {
                if ($p[$j - 1] == '*') {
                    $f[$i][$j] = $f[$i - 1][$j] || $f[$i][$j - 1] || $f[$i - 1][$j - 1];
                } else {
                    $f[$i][$j] =
                        $f[$i - 1][$j - 1] && ($p[$j - 1] == '?' || $s[$i - 1] == $p[$j - 1]);
                }
            }
        }
        return $f[$m][$n];
    }
}

Comments