Regular Expression Matching Solution for Amazon
Company: Amazon · Difficulty: Hard · Topics: String, Dynamic Programming, Recursion
Problem Statement
Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*'.
- '.' Matches any single character.
- '*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
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' once, it becomes "aa".
Example 3:
Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:
Input: s = "aab", p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
Example 5:
Input: s = "mississippi", p = "mis*is*p*."
Output: false
Explanation: The pattern cannot match the entire string.
Intuition
The key insight is to use dynamic programming to handle the complex pattern matching rules. We need to consider all possible ways the pattern can match the string, especially when dealing with '*' which can match zero or more occurrences.
Approach
Approach 1: Dynamic Programming (Optimal)
1. Create a DP table where dp[i][j] = true if s[0...i-1] matches p[0...j-1]
2. Handle base cases (empty string and pattern)
3. Handle different cases: exact match, '.', and '*'
4. For '*', consider zero or more repetitions of the preceding character
Approach 2: Recursive with Memoization
1. Use recursion to try all possible matches
2. Use memoization to avoid redundant calculations
3. Handle the same cases as DP but recursively
Approach 3: Backtracking
1. Use backtracking to try different combinations
2. Less efficient than DP but easier to understand
3. Handle '*' by trying different numbers of repetitions
Dry Run
Let's trace through Example 2: s = "aa", p = "a*"
Dynamic Programming Approach:
- dp[0][0] = true (empty matches empty)
- dp[0][1] = false (empty doesn't match "a")
- dp[0][2] = true (empty matches "a*" with zero repetitions)
- dp[1][0] = false ("a" doesn't match empty)
- dp[1][1] = true ("a" matches "a")
- dp[1][2] = true ("a" matches "a*" with one repetition)
- dp[2][0] = false ("aa" doesn't match empty)
- dp[2][1] = false ("aa" doesn't match "a")
- dp[2][2] = true ("aa" matches "a*" with two repetitions)
Solution
⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.
Solution 1: Dynamic Programming (Optimal)
Time Complexity: O(m*n) - m is string length, n is pattern length
Space Complexity: O(m*n) - DP table
Solution 2: Recursive with Memoization
Time Complexity: O(m*n) - m is string length, n is pattern length
Space Complexity: O(m*n) - Memoization table
Solution 3: Backtracking
Time Complexity: O((m+n)*2^(m+n)) - Exponential in worst case
Space Complexity: O(m+n) - Recursion stack