27. Match a Routing Pattern

Problem

Fin's agent-authored routing rules use a simplified wildcard pattern language to send incoming queries to specialized handlers: . matches any single character, and * matches zero or more occurrences of the character immediately preceding it in the pattern.

Given an incoming query string s and a routing pattern pattern, determine whether the pattern matches the ENTIRE query string, not just a substring of it.

Source: src/27_matches_routing_pattern.py

def is_match(s: str, pattern: str) -> bool: ...

is_match("aa", "a")       # -> False   ("a" only matches one char, s has two)
is_match("aa", "a*")      # -> True    ("a*" matches zero or more "a"s)
is_match("ab", ".*")      # -> True    (".*" matches anything)
is_match("mississippi", "mis*is*p*.")  # -> False

Step-by-Step Approach

1. Let n = len(s), m = len(pattern). Build a (n+1) x (m+1) boolean DP table where dp[i][j] means "s[i:] matches pattern[j:]" — i.e. matching the remaining suffixes.
2. Base case: dp[n][m] = True, since two empty suffixes match.
3. Fill the table backward — i from n down to 0, j from m-1 down to 0 — so that dp[i][j] can rely on already-computed cells to its right/below.
4. At each cell, first check whether the current characters line up: first_match = i < n and pattern[j] in (s[i], ".").
5. If the pattern character after j is a * (pattern[j+1] == "*"), there are two ways to satisfy it: use zero occurrences and skip both pattern[j] and the * (dp[i][j+2]), or, if the current characters match, consume one character of s and stay on the same pattern position (first_match and dp[i+1][j]). dp[i][j] is True if either option works.
6. Otherwise (no following *), the cell is only true if the current characters match AND the rest of the suffixes match: dp[i][j] = first_match and dp[i+1][j+1].
7. The answer is dp[0][0] — do the full strings match from the start?

The key insight is that * makes the "consume one character vs. skip this pattern token" decision reusable at every position, so filling the table from the end backward lets each cell look up already-solved smaller subproblems instead of re-deciding from scratch. Time and space are both O(n * m).

Reference solution

def is_match(s: str, pattern: str) -> bool:
    # dp[i][j] = whether s[i:] matches pattern[j:], filled backward, O(len(s)*len(pattern)) time/space
    n, m = len(s), len(pattern)
    # per-row list, avoids aliasing bug
    dp = [[False] * (m + 1) for _ in range(n + 1)]
    dp[n][m] = True
    # count down to 0 inclusive
    for i in range(n, -1, -1):
        # count down to 0 inclusive
        for j in range(m - 1, -1, -1):
            # bounds-safe char-or-dot match
            first_match = i < n and pattern[j] in (s[i], ".")
            # lookahead: * applies to pattern[j]
            if j + 1 < m and pattern[j + 1] == "*":
                # skip char* (0 reps) or match one more
                dp[i][j] = dp[i][j + 2] or (first_match and dp[i + 1][j])
            else:
                dp[i][j] = first_match and dp[i + 1][j + 1]
    return dp[0][0]

Key Functions & Tricks

• [[False] * (m + 1) for _ in range(n + 1)] — independent per-row list, sized (n+1) x (m+1).
• dp[i][j] — true when s[i:] matches pattern[j:], filled backward.
• range(n, -1, -1) — negative-step range counts down to 0 inclusive.
• first_match = i < n and pattern[j] in (s[i], ".") — bounds-safe char-or-dot match check.
• *-handling — lookahead pattern[j+1] == "*" combines zero-occurrence skip (dp[i][j+2]) with one-more-repeat (dp[i+1][j]) via or.

How to Recognize This Pattern