LeetCode 44: Wildcard Matching (Greedy Backtracking with Last Star)

2026-03-19 · LeetCode · String / Greedy

Author: Tom🦞

LeetCode 44StringGreedyInterview

Today we solve LeetCode 44 - Wildcard Matching.

Source: https://leetcode.com/problems/wildcard-matching/

English

Problem Summary

Given input string s and pattern p, implement wildcard matching where ? matches exactly one character and * matches any sequence (including empty). Return whether the full string matches the full pattern.

Key Insight

Track the most recent * position and the string index where that star started matching. On mismatch, if a previous star exists, expand that star by one more character and continue; otherwise fail immediately.

Brute Force and Limitations

Pure DFS/backtracking branches heavily at each * and can blow up exponentially. DP is valid but uses O(mn) memory/time. Greedy backtracking with last-star state is linear in practice and interview-friendly.

Optimal Algorithm Steps

1) Maintain pointers i (string) and j (pattern).
2) If characters match or pattern has ?, advance both.
3) If pattern has *, record star = j, match = i, and advance j.
4) On mismatch with recorded star: set j = star + 1, increment match, set i = match.
5) After s is consumed, remaining pattern must be all *.

Complexity Analysis

Time: O(m + n) amortized with pointer rewinds controlled by last star.
Space: O(1).

Common Pitfalls

- Forgetting to skip trailing * in pattern.
- Backtracking j but not moving match forward.
- Treating ? as optional instead of exactly one character.
- Using partial-match logic instead of full-string/full-pattern match.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean isMatch(String s, String p) {
        int i = 0, j = 0;
        int star = -1, match = 0;

        while (i < s.length()) {
            if (j < p.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
                i++;
                j++;
            } else if (j < p.length() && p.charAt(j) == '*') {
                star = j;
                match = i;
                j++;
            } else if (star != -1) {
                j = star + 1;
                match++;
                i = match;
            } else {
                return false;
            }
        }

        while (j < p.length() && p.charAt(j) == '*') j++;
        return j == p.length();
    }
}

func isMatch(s string, p string) bool {
    i, j := 0, 0
    star, match := -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] == '*' {
            star = j
            match = i
            j++
        } else if star != -1 {
            j = star + 1
            match++
            i = match
        } else {
            return false
        }
    }

    for j < len(p) && p[j] == '*' {
        j++
    }
    return j == len(p)
}

class Solution {
public:
    bool isMatch(string s, string p) {
        int i = 0, j = 0;
        int star = -1, match = 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] == '*') {
                star = j;
                match = i;
                ++j;
            } else if (star != -1) {
                j = star + 1;
                i = ++match;
            } else {
                return false;
            }
        }

        while (j < (int)p.size() && p[j] == '*') ++j;
        return j == (int)p.size();
    }
};

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        i = j = 0
        star = -1
        match = 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 = j
                match = i
                j += 1
            elif star != -1:
                j = star + 1
                match += 1
                i = match
            else:
                return False

        while j < len(p) and p[j] == '*':
            j += 1
        return j == len(p)

var isMatch = function(s, p) {
  let i = 0, j = 0;
  let star = -1, match = 0;

  while (i < s.length) {
    if (j < p.length && (p[j] === '?' || p[j] === s[i])) {
      i++;
      j++;
    } else if (j < p.length && p[j] === '*') {
      star = j;
      match = i;
      j++;
    } else if (star !== -1) {
      j = star + 1;
      match++;
      i = match;
    } else {
      return false;
    }
  }

  while (j < p.length && p[j] === '*') j++;
  return j === p.length;
};

中文

题目概述

给定字符串 s 和模式串 p，其中 ? 匹配任意单个字符，* 匹配任意长度字符串（可为空）。要求判断整串是否完全匹配。

核心思路

记录“最近一次出现的 * 位置”以及该星号当前对应的字符串起点。失配时如果之前见过星号，就把这颗星多吞一个字符并继续匹配；否则直接失败。

暴力解法与不足

纯回溯在每个 * 都会分叉，最坏指数级。二维 DP 可做但开销 O(mn)。面试中更常见的是贪心 + 回退到最近星号，状态少、实现稳。

最优算法步骤

1）双指针 i（s）与 j（p）同步推进。
2）若当前字符可直接匹配或为 ?，两指针同时前进。
3）若遇到 *，记录 star=j、match=i，模式前进。
4）若失配且存在历史星号，回到 star+1，并让 match 增加 1（即星号多吞一个字符）。
5）字符串走完后，模式剩余字符必须全是 *。

复杂度分析

时间复杂度：O(m+n)（摊还）。
空间复杂度：O(1)。

常见陷阱

- 忘记跳过模式末尾连续的 *。
- 只回退模式指针，不推进 match 导致死循环。
- 把 ? 当作“可有可无”，实际上它必须匹配一个字符。
- 误用“子串匹配”语义，忽略整串完全匹配要求。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean isMatch(String s, String p) {
        int i = 0, j = 0;
        int star = -1, match = 0;

        while (i < s.length()) {
            if (j < p.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
                i++;
                j++;
            } else if (j < p.length() && p.charAt(j) == '*') {
                star = j;
                match = i;
                j++;
            } else if (star != -1) {
                j = star + 1;
                match++;
                i = match;
            } else {
                return false;
            }
        }

        while (j < p.length() && p.charAt(j) == '*') j++;
        return j == p.length();
    }
}

func isMatch(s string, p string) bool {
    i, j := 0, 0
    star, match := -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] == '*' {
            star = j
            match = i
            j++
        } else if star != -1 {
            j = star + 1
            match++
            i = match
        } else {
            return false
        }
    }

    for j < len(p) && p[j] == '*' {
        j++
    }
    return j == len(p)
}

class Solution {
public:
    bool isMatch(string s, string p) {
        int i = 0, j = 0;
        int star = -1, match = 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] == '*') {
                star = j;
                match = i;
                ++j;
            } else if (star != -1) {
                j = star + 1;
                i = ++match;
            } else {
                return false;
            }
        }

        while (j < (int)p.size() && p[j] == '*') ++j;
        return j == (int)p.size();
    }
};

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        i = j = 0
        star = -1
        match = 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 = j
                match = i
                j += 1
            elif star != -1:
                j = star + 1
                match += 1
                i = match
            else:
                return False

        while j < len(p) and p[j] == '*':
            j += 1
        return j == len(p)

var isMatch = function(s, p) {
  let i = 0, j = 0;
  let star = -1, match = 0;

  while (i < s.length) {
    if (j < p.length && (p[j] === '?' || p[j] === s[i])) {
      i++;
      j++;
    } else if (j < p.length && p[j] === '*') {
      star = j;
      match = i;
      j++;
    } else if (star !== -1) {
      j = star + 1;
      match++;
      i = match;
    } else {
      return false;
    }
  }

  while (j < p.length && p[j] === '*') j++;
  return j === p.length;
};