Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:
'.'Matches any single character'*'Matches zero or more of the preceding element
The matching should cover the entire input string (not partial).
Input:
- A string
s(the input string) - A string
p(the pattern)
Output:
- Boolean indicating if the entire string matches the pattern
Constraints:
- 1 ≤ s.length ≤ 20
- 1 ≤ p.length ≤ 30
- s contains only lowercase English letters
- p contains only lowercase English letters, ‘.’, and ‘*’
- It is guaranteed for each 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' 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 2 times. Therefore, it matches "aab".
Solutions
Approach 1: 2D Dynamic Programming
Algorithm:
- Create 2D DP table where dp[i][j] = true if s[0:i] matches p[0:j]
- Base case: dp[0][0] = true (empty string matches empty pattern)
- Handle patterns with ‘*’ that can match zero characters
- For each cell, check character match and handle ‘*’ cases
Python:
def isMatch(s, p):
"""
2D DP solution for regex matching
Time: O(m * n) where m = len(s), n = len(p)
Space: O(m * n) for DP table
"""
m, n = len(s), len(p)
# dp[i][j] = True if s[0:i] matches p[0:j]
dp = [[False] * (n + 1) for _ in range(m + 1)]
# Base case: empty string matches empty pattern
dp[0][0] = True
# Handle patterns like "a*", "a*b*", etc. that can match empty string
for j in range(2, n + 1):
# Pattern like "a*" can match empty string
if p[j-1] == '*':
dp[0][j] = dp[0][j-2]
# Fill DP table
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j-1] == '*':
# '*' can match zero or more of preceding character
# Case 1: Use * to match zero occurrences (ignore "x*")
dp[i][j] = dp[i][j-2]
# Case 2: Use * to match one or more occurrences
# Check if preceding character matches current character in s
if matches(s, p, i, j-1): # s[i-1] matches p[j-2]
dp[i][j] = dp[i][j] or dp[i-1][j]
else:
# Regular character or '.'
if matches(s, p, i, j):
dp[i][j] = dp[i-1][j-1]
return dp[m][n]
def matches(s, p, i, j):
"""Check if s[i-1] matches p[j-1]"""
return p[j-1] == '.' or s[i-1] == p[j-1]
def isMatch_verbose(s, p):
"""
Verbose version with detailed comments
Time: O(m * n)
Space: O(m * n)
"""
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
# Base case
dp[0][0] = True
print(f"Base case: dp[0][0] = {dp[0][0]}")
# Handle patterns that can match empty string
for j in range(2, n + 1):
if p[j-1] == '*':
dp[0][j] = dp[0][j-2]
print(f"Empty string vs '{p[:j]}': dp[0][{j}] = {dp[0][j]}")
# Fill table
for i in range(1, m + 1):
for j in range(1, n + 1):
char_s = s[i-1]
char_p = p[j-1]
if char_p == '*':
# Zero occurrences
dp[i][j] = dp[i][j-2]
# One or more occurrences
if p[j-2] == '.' or s[i-1] == p[j-2]:
dp[i][j] = dp[i][j] or dp[i-1][j]
print(f"s[:{i}]='{s[:i]}' vs p[:{j}]='{p[:j]}' (*): dp[{i}][{j}] = {dp[i][j]}")
else:
# Regular character or '.'
if char_p == '.' or char_s == char_p:
dp[i][j] = dp[i-1][j-1]
print(f"s[:{i}]='{s[:i]}' vs p[:{j}]='{p[:j]}' ({char_p}): dp[{i}][{j}] = {dp[i][j]}")
return dp[m][n]
# Example usage
print(isMatch("aa", "a*")) # Output: True
print(isMatch("ab", ".*")) # Output: True
print(isMatch("aab", "c*a*b")) # Output: True
Java:
class Solution {
/**
* 2D DP solution for regex matching
* Time: O(m * n)
* Space: O(m * n)
*/
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
// dp[i][j] = true if s[0:i] matches p[0:j]
boolean[][] dp = new boolean[m + 1][n + 1];
// Base case
dp[0][0] = true;
// Handle patterns like "a*", "a*b*" that can match empty string
for (int j = 2; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = dp[0][j - 2];
}
}
// Fill DP table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
// '*' can match zero or more of preceding character
// Case 1: zero occurrences
dp[i][j] = dp[i][j - 2];
// Case 2: one or more occurrences
if (matches(s, p, i, j - 1)) {
dp[i][j] = dp[i][j] || dp[i - 1][j];
}
} else {
// Regular character or '.'
if (matches(s, p, i, j)) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
}
return dp[m][n];
}
private boolean matches(String s, String p, int i, int j) {
return p.charAt(j - 1) == '.' || s.charAt(i - 1) == p.charAt(j - 1);
}
}
Approach 2: Recursion with Memoization
Python:
def isMatch_recursive(s, p):
"""
Recursive solution with memoization
Time: O(m * n)
Space: O(m * n) for memoization + recursion stack
"""
memo = {}
def dp(i, j):
# Base cases
if (i, j) in memo:
return memo[(i, j)]
# If pattern is exhausted
if j == len(p):
return i == len(s)
# Check if current characters match
first_match = i < len(s) and (p[j] == '.' or s[i] == p[j])
# Handle '*' in pattern
if j + 1 < len(p) and p[j + 1] == '*':
# Two choices:
# 1. Don't use the "x*" pattern (match zero occurrences)
# 2. Use the "x*" pattern if first character matches
result = (dp(i, j + 2) or
(first_match and dp(i + 1, j)))
else:
# No '*', must match current character
result = first_match and dp(i + 1, j + 1)
memo[(i, j)] = result
return result
return dp(0, 0)
def isMatch_recursive_verbose(s, p):
"""
Verbose recursive solution
Time: O(m * n)
Space: O(m * n)
"""
memo = {}
def dp(i, j, depth=0):
indent = " " * depth
print(f"{indent}Checking s[{i}:] = '{s[i:]}' vs p[{j}:] = '{p[j:]}'")
if (i, j) in memo:
print(f"{indent}Found in memo: {memo[(i, j)]}")
return memo[(i, j)]
# Pattern exhausted
if j == len(p):
result = i == len(s)
print(f"{indent}Pattern exhausted, string exhausted: {result}")
memo[(i, j)] = result
return result
# Check current character match
first_match = i < len(s) and (p[j] == '.' or s[i] == p[j])
print(f"{indent}First match: {first_match}")
if j + 1 < len(p) and p[j + 1] == '*':
print(f"{indent}Found '*' pattern: {p[j]}*")
# Zero occurrences
zero_match = dp(i, j + 2, depth + 1)
print(f"{indent}Zero occurrences: {zero_match}")
# One or more occurrences
if first_match:
one_or_more = dp(i + 1, j, depth + 1)
print(f"{indent}One or more occurrences: {one_or_more}")
result = zero_match or one_or_more
else:
result = zero_match
else:
print(f"{indent}Regular character match")
result = first_match and dp(i + 1, j + 1, depth + 1)
print(f"{indent}Result: {result}")
memo[(i, j)] = result
return result
return dp(0, 0)
# Example usage
print(isMatch_recursive("aab", "c*a*b")) # Output: True
Key Insights
- Two Key Cases: Handle regular characters/dots and ‘*’ patterns differently
- ’*’ Flexibility: ‘*’ can match zero or more of the preceding character
- Greedy vs Non-greedy: ‘*’ requires checking both zero and multiple matches
- Base Cases: Empty pattern can only match empty string (with exceptions)
- State Definition: dp[i][j] represents if s[0:i] matches p[0:j]
Edge Cases
- Empty strings: Both empty should return True
- Pattern with ‘*’: “a*” can match empty string
- Only ‘.’: Single ‘.’ matches any single character
- Only ‘*’: Invalid pattern (guaranteed not to happen)
- Multiple ‘*’: “ab” can match various combinations
Test Cases
def test_regex_matching():
test_cases = [
("aa", "a", False),
("aa", "a*", True),
("ab", ".*", True),
("aab", "c*a*b", True),
("mississippi", "mis*is*p*.", False),
("", ".*", True),
("", "a*", True),
("a", "ab*", True),
("abc", "a.*c", True),
("abcdef", "a.*f", True)
]
for s, p, expected in test_cases:
result = isMatch(s, p)
assert result == expected, f"s='{s}', p='{p}', expected={expected}, got={result}"
print(f"isMatch('{s}', '{p}') = {result} ✓")
test_regex_matching()
Common Mistakes
- Wrong ‘*’ handling: Not considering both zero and multiple matches
- Index errors: Off-by-one errors when accessing string characters
- Base case confusion: Not handling empty string/pattern correctly
- Greedy matching: Assuming ‘*’ should always match as much as possible
- ’.’ misunderstanding: Forgetting that ‘.’ matches any single character
Follow-up Questions
- Wildcard matching: Different pattern with ‘?’ and ‘*’
- Multiple patterns: Match against multiple regex patterns
- Case sensitivity: Handle case-insensitive matching
- Extended regex: Support for ‘+’, ‘?’, character classes
- Pattern validation: Check if the pattern itself is valid
- Space optimization: Reduce space complexity of DP solution
Interview Tips
- Understand the problem: Clarify what ‘.’ and ‘*’ mean exactly
- Start with examples: Work through examples to understand patterns
- Break down cases: Handle ‘*’ and regular characters separately
- Draw DP table: Visualize the state transitions
- Test edge cases: Empty strings, patterns with multiple ‘*’
- Explain both approaches: Both recursive and iterative DP
- Discuss complexity: Time and space complexity analysis