Sequence pattern matching

Link: wildcard-matching

Problem Statement

You are given two strings:

• s (the input string)

• p (the pattern string)

The pattern string can contain:

• '?' → matches exactly one character

• '*' → matches any sequence of characters (including the empty sequence)

Return true if the entire string s matches the pattern p.

Examples

Example 1:

Input: s = "adceb", p = "*a*b"
Output: true

Example 2:

Input: s = "acdcb", p = "a*c?b"
Output: false

Intuition

This is a classic pattern-matching problem. Use Dynamic Programming to simulate all matching conditions:

• '?' matches any single character.

• '*' matches zero or more characters — we have two choices:

  • Treat '*' as matching zero characters: move j back (dp[i][j-1])

  • Treat '*' as matching one or more characters: move i back (dp[i-1][j])

1. Recursive Approach (TLE for large inputs)

class Solution {
    public boolean isMatch(String s, String p) {
        return helper(s, p, s.length(), p.length());
    }

    private boolean helper(String s, String p, int i, int j) {
        if (i == 0 && j == 0) return true;
        if (j == 0) return false;
        if (i == 0) {
            for (int k = 0; k < j; k++) {
                if (p.charAt(k) != '*') return false;
            }
            return true;
        }

        char sc = s.charAt(i - 1);
        char pc = p.charAt(j - 1);

        if (pc == sc || pc == '?') {
            return helper(s, p, i - 1, j - 1);
        } else if (pc == '*') {
            return helper(s, p, i - 1, j) || helper(s, p, i, j - 1);
        } else {
            return false;
        }
    }
}

Time Complexity: Exponential
Space Complexity: O(n) (recursion stack)

2. Memoization (Top-down DP)

class Solution {
    Boolean[][] dp;

    public boolean isMatch(String s, String p) {
        int n = s.length(), m = p.length();
        dp = new Boolean[n + 1][m + 1];
        return match(s, p, n, m);
    }

    private boolean match(String s, String p, int i, int j) {
        if (i == 0 && j == 0) return true;
        if (j == 0) return false;
        if (i == 0) {
            for (int k = 0; k < j; k++) {
                if (p.charAt(k) != '*') return false;
            }
            return true;
        }

        if (dp[i][j] != null) return dp[i][j];

        char sc = s.charAt(i - 1);
        char pc = p.charAt(j - 1);

        if (pc == sc || pc == '?') {
            return dp[i][j] = match(s, p, i - 1, j - 1);
        } else if (pc == '*') {
            return dp[i][j] = match(s, p, i - 1, j) || match(s, p, i, j - 1);
        } else {
            return dp[i][j] = false;
        }
    }
}

Time Complexity: O(n * m)
Space Complexity: O(n * m)

3. Tabulation (Bottom-up DP)

class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length(), m = p.length();
        boolean[][] dp = new boolean[n + 1][m + 1];

        dp[0][0] = true;

        for (int j = 1; j <= m; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 1];
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                char sc = s.charAt(i - 1);
                char pc = p.charAt(j - 1);

                if (pc == sc || pc == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pc == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                } else {
                    dp[i][j] = false;
                }
            }
        }

        return dp[n][m];
    }
}

Time Complexity: O(n * m)
Space Complexity: O(n * m)

4. Space Optimized DP (1D)

class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length(), m = p.length();
        boolean[] prev = new boolean[m + 1];
        boolean[] curr = new boolean[m + 1];

        prev[0] = true;

        for (int j = 1; j <= m; j++) {
            if (p.charAt(j - 1) == '*') {
                prev[j] = prev[j - 1];
            }
        }

        for (int i = 1; i <= n; i++) {
            curr[0] = false;
            for (int j = 1; j <= m; j++) {
                if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '?') {
                    curr[j] = prev[j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    curr[j] = curr[j - 1] || prev[j];
                } else {
                    curr[j] = false;
                }
            }
            prev = curr.clone();
        }

        return prev[m];
    }
}

Time Complexity: O(n * m)
Space Complexity: O(m)

Summary Table

Key Observations

• '?' always matches exactly one character.

• '*' can match:

  • No character → dp[i][j - 1]

  • One or more characters → dp[i - 1][j]

• Edge case: when s is empty, p must contain only * to return true.