Pattern Match

TIP103 Unit 12 Session 2 (Click for link to problem statements)

Pattern Match

Implement pattern matching over an input string s and a pattern p, where . matches any single character and * matches zero or more of the character immediately before it. The match must cover the entire input string.

Return True if p matches all of s, otherwise False.

def is_match(s, p):
    pass

Problem Highlights

• 💡 Difficulty: Hard
• ⏰ Time to complete: 35-45 mins
• 🛠️ Topics: Dynamic Programming, Strings, Recursion

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: Does the pattern need to match the entire string, or just part of it?

  • A: The pattern must match the entire input string s. A partial match, such as p = "a" against s = "aa", returns False.

• Q: What does * apply to? Can it appear on its own?

  • A: * always modifies the single character immediately before it, meaning "zero or more of that character." So a* can match "", "a", "aa", and so on. A well-formed pattern never starts with *.

• Q: What happens when . and * are combined, as in .*?

  • A: . matches any one character, so .* matches zero or more of any character — it can absorb any string, including the empty string.

HAPPY CASE
Input: s = "aa", p = "a"
Output: False
Explanation: "a" matches only a single 'a'; it cannot cover the entire string "aa".

Input: s = "aa", p = "a*"
Output: True
Explanation: "a*" means zero or more of 'a', so it can expand to match "aa".

Input: s = "ab", p = ".*"
Output: True
Explanation: ".*" means zero or more of any character, so it matches "ab".

EDGE CASE
Input: s = "", p = "a*"
Output: True
Explanation: "a*" can match zero occurrences of 'a', so it matches the empty string.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For String Matching Problems with wildcard characters, we can consider the following approaches:

• Dynamic Programming (2D): Whether s[:i] matches p[:j] depends only on smaller prefixes of s and p, giving overlapping subproblems and optimal substructure — the classic signal for a 2D DP table indexed by positions in both strings.
• Recursion with Memoization: The same subproblem structure can be solved top-down by recursing on (i, j) pairs and caching results. Naive recursion without memoization branches exponentially on every *.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Build a 2D boolean table dp where dp[i][j] means "the first i characters of s match the first j characters of p." The empty pattern matches the empty string, so dp[0][0] = True. Then fill the table row by row: a literal character or . extends a match diagonally, while a * either drops its preceding character entirely (zero occurrences, look two columns left) or consumes one more matching character of s (look one row up). The answer is dp[len(s)][len(p)].

1) Let m = len(s) and n = len(p). Create a (m+1) x (n+1) table `dp` filled with False.
2) Set dp[0][0] = True, since an empty pattern matches an empty string.
3) Fill the first row: for each j, if p[j-1] == '*', set dp[0][j] = dp[0][j-2].
   (Patterns like "a*", "a*b*" can match the empty string by using zero occurrences.)
4) For each i from 1 to m, and each j from 1 to n:
   a) If p[j-1] == '*':
      - Zero occurrences of the preceding character: dp[i][j] = dp[i][j-2]
      - One or more occurrences: if p[j-2] is '.' or equals s[i-1],
        also allow dp[i][j] = dp[i-1][j]
   b) Else if p[j-1] == '.' or p[j-1] == s[i-1]:
      - dp[i][j] = dp[i-1][j-1]
5) Return dp[m][n].

⚠️ Common Mistakes

• Forgetting to initialize the first row for patterns like a* or a*b* that can match the empty string.
• Treating * as a standalone wildcard instead of a modifier on the character before it (looking back one column instead of two for the zero-occurrence case).
• Only checking the zero-occurrence branch of * and forgetting the "consume one more character" branch (dp[i-1][j]), or vice versa.
• Returning a prefix match instead of requiring the pattern to cover the entire string.

4: I-mplement

Implement the code to solve the algorithm.

def is_match(s, p):
    m, n = len(s), len(p)
    # dp[i][j] = True if s[:i] matches p[:j]
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True  # Empty pattern matches empty string

    # Patterns like a*, a*b*, a*b*c* can match the empty string
    for j in range(1, n + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 2]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                # Zero occurrences of the preceding character
                dp[i][j] = dp[i][j - 2]
                # One or more occurrences, if the preceding character matches s[i-1]
                if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
                    dp[i][j] = dp[i][j] or dp[i - 1][j]
            elif p[j - 1] == '.' or p[j - 1] == s[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]

    return dp[m][n]

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: s = "aa", p = "a"

  • dp[0][0] = True; dp[1][1] = True ('a' matches 'a').
  • dp[2][1] stays False: the pattern has no characters left to cover the second 'a'.
  • Output: False

• Input: s = "aa", p = "a*"

  • dp[0][2] = True ("a*" matches empty via zero occurrences).
  • dp[1][2] = True (one 'a', via dp[0][2] using the one-or-more branch).
  • dp[2][2] = True (two 'a's, via dp[1][2]).
  • Output: True

• Input: s = "ab", p = ".*"

  • dp[0][2] = True (".*" matches empty).
  • dp[1][2] = True ('.' absorbs 'a' via dp[0][2]); dp[2][2] = True ('.' absorbs 'b' via dp[1][2]).
  • Output: True

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume M is the length of the input string s and N is the length of the pattern p.

• Time Complexity: O(M * N) because we fill each cell of the (M+1) x (N+1) DP table exactly once with constant work per cell.
• Space Complexity: O(M * N) for the DP table. This can be reduced to O(N) by keeping only the current and previous rows, since each cell depends only on the current row and the row above.