Wildcard Matching

Problem#

Implement matching with ? (any single char) and * (any sequence including empty). Return true iff the entire s is matched by p.

Examples#

s = "aa", p = "*" → true
s = "cb", p = "?a" → false
s = "adceb", p = "*a*b" → true

Constraints#

0 <= n, m <= 2000.

Approach#

DP — dp[i][j] = does s[0..i-1] match p[0..j-1]. O(n × m).

Greedy two-pointer with backtrack — O(n + m) average. Remember the last * and the position in s to backtrack to on mismatch.

Solution#

class Solution {
public:
    bool isMatch(string s, string p) {
        int i = 0, j = 0, starIdx = -1, sBack = 0;
        while (i < (int)s.size()) {
            if (j < (int)p.size() && (p[j] == '?' || p[j] == s[i])) {
                ++i; ++j;
            } else if (j < (int)p.size() && p[j] == '*') {
                starIdx = j; sBack = i; ++j;
            } else if (starIdx != -1) {
                j = starIdx + 1;
                i = ++sBack;
            } else {
                return false;
            }
        }
        while (j < (int)p.size() && p[j] == '*') ++j;
        return j == (int)p.size();
    }
};

func isMatch(s string, p string) bool {
    i, j, starIdx, sBack := 0, 0, -1, 0
    for i < len(s) {
        if j < len(p) && (p[j] == '?' || p[j] == s[i]) {
            i++
            j++
        } else if j < len(p) && p[j] == '*' {
            starIdx = j
            sBack = i
            j++
        } else if starIdx != -1 {
            j = starIdx + 1
            sBack++
            i = sBack
        } else {
            return false
        }
    }
    for j < len(p) && p[j] == '*' {
        j++
    }
    return j == len(p)
}

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        i, j, star_idx, s_back = 0, 0, -1, 0
        while i < len(s):
            if j < len(p) and (p[j] == '?' or p[j] == s[i]):
                i += 1
                j += 1
            elif j < len(p) and p[j] == '*':
                star_idx = j
                s_back = i
                j += 1
            elif star_idx != -1:
                j = star_idx + 1
                s_back += 1
                i = s_back
            else:
                return False
        while j < len(p) and p[j] == '*':
            j += 1
        return j == len(p)

function isMatch(s, p) {
    let i = 0, j = 0, starIdx = -1, sBack = 0;
    while (i < s.length) {
        if (j < p.length && (p[j] === '?' || p[j] === s[i])) {
            i++;
            j++;
        } else if (j < p.length && p[j] === '*') {
            starIdx = j;
            sBack = i;
            j++;
        } else if (starIdx !== -1) {
            j = starIdx + 1;
            sBack++;
            i = sBack;
        } else {
            return false;
        }
    }
    while (j < p.length && p[j] === '*') j++;
    return j === p.length;
}

class Solution {
    public boolean isMatch(String s, String p) {
        int i = 0, j = 0, starIdx = -1, sBack = 0;
        int n = s.length(), m = p.length();
        while (i < n) {
            if (j < m && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
                i++;
                j++;
            } else if (j < m && p.charAt(j) == '*') {
                starIdx = j;
                sBack = i;
                j++;
            } else if (starIdx != -1) {
                j = starIdx + 1;
                sBack++;
                i = sBack;
            } else {
                return false;
            }
        }
        while (j < m && p.charAt(j) == '*') j++;
        return j == m;
    }
}

function isMatch(s: string, p: string): boolean {
    let i = 0, j = 0, starIdx = -1, sBack = 0;
    while (i < s.length) {
        if (j < p.length && (p[j] === '?' || p[j] === s[i])) {
            i++;
            j++;
        } else if (j < p.length && p[j] === '*') {
            starIdx = j;
            sBack = i;
            j++;
        } else if (starIdx !== -1) {
            j = starIdx + 1;
            sBack++;
            i = sBack;
        } else {
            return false;
        }
    }
    while (j < p.length && p[j] === '*') j++;
    return j === p.length;
}

Editorial#

The greedy backtracks only to the most recent * — it represents the “we can absorb more characters” decision. On mismatch, extend the absorption by one character (advance sBack and reset j to one past the star). Any trailing *s in p after s is consumed are free matches.

Complexity#

Time: O(n + m) average; O(n × m) worst.
Space: O(1).

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#