Regular Expression Matching - Practice Coding Problems

Regular Expression Matching - Problem

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 & Output

Example 1 — Basic Star Pattern

$ Input: s = "aa", p = "a*"

› Output: true

💡 Note: The pattern 'a*' means zero or more 'a' characters. Since the string contains exactly two 'a's, the pattern matches.

Example 2 — Dot Wildcard

$ Input: s = "ab", p = ".*"

› Output: true

💡 Note: The pattern '.*' means zero or more of any character. This can match any string, including 'ab'.

Example 3 — No Match

$ Input: s = "mississippi", p = "mis*is*p*."

› Output: false

💡 Note: The pattern expects one more character at the end (the '.'), but the string ends after 'i'.

Constraints

1 ≤ s.length ≤ 20
1 ≤ p.length ≤ 30
s contains only lowercase English letters
p contains only lowercase English letters, '.', and '*'
'*' always appears after a preceding element

Visualization

Tap to expand

Understanding the Visualization

Input

String s="aa" and pattern p="a*"

Process

Check if pattern can match entire string

Output

Return true if complete match found

Key Takeaway

🎯 Key Insight: Use dynamic programming to handle overlapping subproblems when matching patterns with wildcards

Asked in

G Google 45 a Amazon 38 f Facebook 32 M Microsoft 28

The key insight is to break the problem into subproblems: does s[0..i] match p[0..j]? Handle the '*' character by trying both zero matches and one-or-more matches. Best approach is Dynamic Programming with O(m×n) time and space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Recursion with Memoization	O(m×n)	O(m×n)	Cache results of subproblems to avoid redundant calculations
Recursive Brute Force	O(2^(m+n))	O(m+n)	Try all possible ways the pattern could match using recursion
Dynamic Programming (Bottom-Up)	O(m×n)	O(m×n)	Build a 2D table to solve all subproblems iteratively from bottom-up

Recursion with Memoization — Algorithm Steps

Step 1: Create a memoization table to store results
Step 2: Before recursing, check if result already computed
Step 3: Compute result using same recursive logic as brute force
Step 4: Store result in memo table before returning

Visualization

Tap to expand

Step-by-Step Walkthrough

First Call

Calculate and store result in memo table

Repeat Call

Return cached result instead of recalculating

Speedup

Each subproblem solved only once

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>

#define MAX_LEN 1000

int memo[MAX_LEN][MAX_LEN];
int memo_init = 0;

bool helper(const char* s, const char* p, int i, int j) {
    int s_len = strlen(s);
    int p_len = strlen(p);
    
    if (!memo_init) {
        for (int x = 0; x < MAX_LEN; x++) {
            for (int y = 0; y < MAX_LEN; y++) {
                memo[x][y] = -1;
            }
        }
        memo_init = 1;
    }
    
    if (memo[i][j] != -1) {
        return memo[i][j];
    }
    
    bool result;
    // Base case: pattern exhausted
    if (j >= p_len) {
        result = i >= s_len;
    } else {
        // Check if current characters match
        bool firstMatch = i < s_len && (p[j] == s[i] || p[j] == '.');
        
        // Handle '*' case
        if (j + 1 < p_len && p[j + 1] == '*') {
            // Try zero matches or one-or-more matches
            result = helper(s, p, i, j + 2) || (firstMatch && helper(s, p, i + 1, j));
        } else {
            // Normal character match
            result = firstMatch && helper(s, p, i + 1, j + 1);
        }
    }
    
    memo[i][j] = result;
    return result;
}

bool solution(const char* s, const char* p) {
    memo_init = 0;
    return helper(s, p, 0, 0);
}

int main() {
    char s[MAX_LEN], p[MAX_LEN];
    fgets(s, sizeof(s), stdin);
    fgets(p, sizeof(p), stdin);
    s[strcspn(s, "\n")] = 0;
    p[strcspn(p, "\n")] = 0;
    bool result = solution(s, p);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Each of the m×n subproblems is computed exactly once

✓ Linear Growth

Space Complexity

O(m×n)

Memoization table stores results for all (i,j) pairs plus recursion stack

⚡ Linearithmic Space

280.5K Views

High Frequency

~35 min Avg. Time

8.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursion with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler