Regular Expression Matching (LC 10)

Implement regular expression matching with '.' and '*'

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:

  1. Create 2D DP table where dp[i][j] = true if s[0:i] matches p[0:j]
  2. Base case: dp[0][0] = true (empty string matches empty pattern)
  3. Handle patterns with ‘*’ that can match zero characters
  4. 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

  1. Two Key Cases: Handle regular characters/dots and ‘*’ patterns differently
  2. ’*’ Flexibility: ‘*’ can match zero or more of the preceding character
  3. Greedy vs Non-greedy: ‘*’ requires checking both zero and multiple matches
  4. Base Cases: Empty pattern can only match empty string (with exceptions)
  5. State Definition: dp[i][j] represents if s[0:i] matches p[0:j]

Edge Cases

  1. Empty strings: Both empty should return True
  2. Pattern with ‘*’: “a*” can match empty string
  3. Only ‘.’: Single ‘.’ matches any single character
  4. Only ‘*’: Invalid pattern (guaranteed not to happen)
  5. 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

  1. Wrong ‘*’ handling: Not considering both zero and multiple matches
  2. Index errors: Off-by-one errors when accessing string characters
  3. Base case confusion: Not handling empty string/pattern correctly
  4. Greedy matching: Assuming ‘*’ should always match as much as possible
  5. ’.’ misunderstanding: Forgetting that ‘.’ matches any single character

Follow-up Questions

  1. Wildcard matching: Different pattern with ‘?’ and ‘*’
  2. Multiple patterns: Match against multiple regex patterns
  3. Case sensitivity: Handle case-insensitive matching
  4. Extended regex: Support for ‘+’, ‘?’, character classes
  5. Pattern validation: Check if the pattern itself is valid
  6. Space optimization: Reduce space complexity of DP solution

Interview Tips

  1. Understand the problem: Clarify what ‘.’ and ‘*’ mean exactly
  2. Start with examples: Work through examples to understand patterns
  3. Break down cases: Handle ‘*’ and regular characters separately
  4. Draw DP table: Visualize the state transitions
  5. Test edge cases: Empty strings, patterns with multiple ‘*’
  6. Explain both approaches: Both recursive and iterative DP
  7. Discuss complexity: Time and space complexity analysis