Katkat
Back

Implement Regular Expression Matching

AmazonSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to handle recursive string matching problems using dynamic programming, specifically focusing on handling wildcard and repetition operators.

Problem Statement

Implement a function is_match(s, p) that implements regular expression support with the following rules:

  • . matches any single character.
  • * matches zero or more of the preceding element.

The matching should cover the entire input string s (not a partial match). The pattern p contains only lowercase English letters and the characters . or *.

Function Signature

def is_match(s: str, p: str) -> bool:

Constraints

  • 0 <= s.length <= 20
  • 0 <= p.length <= 20
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '.', and '*'.
  • It is guaranteed that for every appearance of *, there will be a previous valid character to match.

Examples

Example 1: Input: s = "aa", p = "a" Output: false Explanation: "a" does not match the entire string "aa".

Example 2: Input: s = "aa", p = "a*" Output: true Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' twice, it becomes "aa".

Example 3: Input: s = "ab", p = ".*" Output: true Explanation: "." means "zero or more () of any character (.)".

Edge Cases

  • Empty strings matching empty patterns.
  • Patterns that start with * (though usually invalid, handle gracefully if needed).
  • Multiple * sequences like a*b*c* matching an empty string.

Hints

Hint 1

Consider using a 2D boolean array `dp[i][j]` where `dp[i][j]` represents whether the first `i` characters of `s` match the first `j` characters of `p`.

Hint 2

If `p[j-1]` is a character, the match depends on `s[i-1] == p[j-1]` and the previous state `dp[i-1][j-1]`.

Hint 3

If `p[j-1]` is `*`, you have two scenarios: zero occurrences of the preceding element (look at `dp[i][j-2]`) or one/more occurrences if the preceding element matches `s[i-1]` (look at `dp[i-1][j]`).

Follow-up questions

  • How would you optimize the space complexity if you only need the previous row of the DP table?
  • How would you modify the algorithm to support a '+' operator (matching one or more of the preceding element)?
  • What is the time complexity of your solution in terms of the lengths of `s` and `p`?