Regular Expression Matching Solution for Microsoft
Company: Microsoft · 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.
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 doesn't match the entire string.
Intuition
The key insight is that this is a dynamic programming problem where we need to match the string against the pattern character by character, handling the special cases of '.' and '*' appropriately. The '*' character is particularly tricky as it can match zero or more of the preceding character, which requires us to consider multiple possibilities.
Approach
Approach 1: Dynamic Programming (Optimal)
1. Create a 2D DP table where dp[i][j] represents if s[0...i-1] matches p[0...j-1]
2. Handle base cases: empty string and empty pattern
3. For each character in pattern:
- If it's a regular character or '.', check if it matches current string character
- If it's '*', handle zero or more repetitions of the preceding character
4. Fill the DP table bottom-up
Approach 2: Recursion with Memoization
1. Use recursive function with memoization
2. Handle each case: regular character, '.', and '*'
3. Cache results to avoid redundant calculations
Approach 3: Backtracking
1. Try all possible matches for '*' patterns
2. Backtrack when a match fails
3. Time complexity can be exponential in worst case
Dry Run
Let's trace through Example 2: s = "aa", p = "a*"
DP Approach:
- Initialize dp[0][0] = true (empty matches empty)
- dp[0][1] = false (empty string doesn't match "a")
- dp[0][2] = true (empty string matches "a*" with zero repetitions)
- dp[1][0] = false (non-empty string doesn't match empty pattern)
- dp[1][1] = true (first 'a' matches first 'a')
- dp[1][2] = true (second 'a' matches "a*" with one repetition)
Recursion Approach:
- s="aa", p="a*"
- firstMatch = true (first characters match)
- Check p[1] = '*'
- Try zero occurrence: isMatch("aa", "") = false
- Try one occurrence: isMatch("a", "a*") = true
- Result: true
Solution
Note: This solution provides multiple approaches to solve the problem. Choose the one that best fits your understanding and requirements.
Key Insights:
1. DP Approach: The key insight is building the solution incrementally using a 2D table
2. Star Handling: When we encounter '*', we need to consider both zero and one-or-more occurrences
3. Base Cases: Empty pattern matches empty string, but not non-empty strings
Edge Cases:
- Empty string with empty pattern: true
- Empty string with non-empty pattern: depends on pattern
- Non-empty string with empty pattern: false
- Pattern with consecutive stars: handled by DP logic
Time Complexity
- Best Case: O(m*n) - DP approach where m and n are lengths of string and pattern
- Average Case: O(m*n) - DP approach
- Worst Case: O(2^(m+n)) - Backtracking approach
Space Complexity
- Best Case: O(m*n) - DP table
- Average Case: O(m*n) - DP approach
- Worst Case: O(m*n) - Memoization table