Regular Expression Matching

📋

Problem

Imagine building a search engine that supports complex pattern queries with '.' and '*' wildcards, and you need to verify if a given text matches a pattern.

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). Return true if s matches p, otherwise false.

1 ≤ s.length, p.length ≤ 1000s contains only lowercase English lettersp contains only lowercase English letters, '.' and '*'

Edge cases: Empty string s and empty pattern p → trueEmpty string s and pattern with only '*' (like 'a*') → truePattern with '*' at the start (invalid pattern) → should handle gracefully

</>

IDE

def isMatch(s: str, p: str) -> bool:public boolean isMatch(String s, String p)bool isMatch(string s, string p)function isMatch(s, p)

def isMatch(s: str, p: str) -> bool:
    # Write your solution here
    pass

class Solution {
    public boolean isMatch(String s, String p) {
        // Write your solution here
        return false;
    }
}

#include <string>
using namespace std;

bool isMatch(string s, string p) {
    // Write your solution here
    return false;
}

function isMatch(s, p) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: true for input s='aa', p='a'Failed to enforce full string match; pattern shorter than string but returned true.✅ Ensure that the entire string is matched by the pattern, not just a prefix.

Wrong: false for input s='aab', p='c*a*b'Did not handle '*' zero occurrence correctly, skipping 'c*' and 'a*'.✅ Add logic to try skipping '*' and consuming characters when matching.

Wrong: false for input s='', p='a*'Failed to initialize dp for patterns that can match empty string via '*'.✅ Initialize dp[0][j] = dp[0][j-2] when p[j-1] == '*'.

Wrong: true for input s='a', p='*a'Did not validate pattern correctness; '*' cannot be first character.✅ Add validation to reject patterns starting with '*'.

Wrong: false for input s='aaa', p='a*a'Used greedy matching consuming all 'a's leaving no match for last 'a'.✅ Try both skipping '*' and consuming characters in DP.

✓

Test Cases

Focus on handling empty strings and patterns, especially '*' matching zero occurrences.

Watch out for greedy matching traps and ensure your DP covers all cases.

Optimize your solution to run in O(m*n) time to handle large inputs efficiently.

t1_01basic

Input{"s":"aa","p":"a"}

Expectedfalse

⏱ Performance - must finish in 2000ms

Pattern 'a' does not match the entire string 'aa'.

💡 Consider how the pattern length compares to the string length.

💡 Check if the pattern can match multiple characters or just one.

💡 Remember '*' allows zero or more of the preceding element; here there's no '*'.

Why it failed: Returned true incorrectly - failed to enforce full string match or ignored pattern length. Fix by ensuring pattern matches entire string length and handle '*' correctly.

✓ Correctly identified no full match for pattern 'a' against 'aa'.

t1_02basic

Input{"s":"aab","p":"c*a*b"}

Expectedtrue

⏱ Performance - must finish in 2000ms

Pattern 'c*a*b' matches 'aab' by interpreting 'c*' as empty, 'a*' as 'aa', and 'b' as 'b'.

💡 Try to interpret '*' as zero or more of the preceding character.

💡 Use recursion or DP to explore both skipping and consuming characters with '*'.

💡 Implement dp[i][j] = dp[i][j+2] (skip '*') or (first_match and dp[i+1][j]) (consume '*').

Why it failed: Returned false incorrectly - failed to handle '*' zero occurrence or multiple occurrences properly. Fix by adding logic to try skipping '*' or consuming matching characters.

✓ Correctly matched complex pattern with '*' against string.

t2_01edge

Input{"s":"","p":""}

Expectedtrue

⏱ Performance - must finish in 2000ms

Empty string matches empty pattern.

💡 Check base case when both string and pattern are empty.

💡 DP base case dp[0][0] should be true.

💡 Return true if both s and p are empty at the same time.

Why it failed: Returned false incorrectly - failed to handle empty string and empty pattern base case. Fix by initializing dp[0][0] = true.

✓ Correctly handled empty string and empty pattern match.

t2_02edge

Input{"s":"","p":"a*"}

Expectedtrue

⏱ Performance - must finish in 2000ms

Pattern 'a*' can match empty string by zero occurrences of 'a'.

💡 Consider '*' can represent zero occurrences of preceding char.

💡 Initialize dp for patterns like 'a*' matching empty string.

💡 Set dp[0][j] = dp[0][j-2] if p[j-1] == '*'.

Why it failed: Returned false incorrectly - failed to handle '*' matching zero occurrences at start. Fix by initializing dp row 0 for patterns with '*'.

✓ Correctly matched empty string with pattern containing '*'.

t2_03edge

Input{"s":"a","p":"*a"}

Expectedfalse

⏱ Performance - must finish in 2000ms

Pattern starting with '*' is invalid and should not match any string.

💡 Check if pattern starts with '*' which is invalid.

💡 Handle invalid patterns gracefully by returning false.

💡 Add validation to reject patterns with '*' at position 0.

Why it failed: Returned true incorrectly - failed to reject invalid pattern starting with '*'. Fix by validating pattern before matching.

✓ Correctly rejected pattern starting with '*'.

t3_01corner

Input{"s":"aaa","p":"a*a"}

Expectedtrue

⏱ Performance - must finish in 2000ms

Pattern 'a*a' matches 'aaa' by 'a*' matching 'aa' and final 'a' matching last 'a'.

💡 Beware greedy matching consuming too many characters.

💡 Try both skipping '*' and consuming characters to find correct match.

💡 Implement dp to explore all possibilities of '*' usage.

Why it failed: Returned false incorrectly - greedy approach consumed all 'a's leaving no match for last 'a'. Fix by trying both skip and consume options for '*'.

✓ Correctly handled greedy trap by exploring all '*' usages.

t3_02corner

Input{"s":"ab","p":".*c"}

Expectedfalse

⏱ Performance - must finish in 2000ms

Pattern '.*c' cannot match 'ab' because 'c' must match last char but string ends with 'b'.

💡 Check that '.' matches any single char but final char must match exactly.

💡 Ensure pattern length matches string length after expansion.

💡 Use DP to verify full pattern coverage, not partial.

Why it failed: Returned true incorrectly - failed to enforce full pattern match including last character. Fix by ensuring dp covers entire pattern and string.

✓ Correctly rejected partial matches where pattern length mismatch.

t3_03corner

Input{"s":"aaa","p":"ab*a*c*a"}

Expectedtrue

⏱ Performance - must finish in 2000ms

Complex pattern matches 'aaa' by interpreting 'b*' as empty, 'a*' as 'aa', and final 'a'.

💡 Handle multiple '*' in pattern carefully.

💡 Use DP to combine zero or more occurrences for each '*'.

💡 Check all branches where '*' can match zero or more chars.

Why it failed: Returned false incorrectly - failed to handle multiple '*' correctly in pattern. Fix by implementing full DP with all '*' branches.

✓ Correctly matched complex pattern with multiple '*' operators.

t4_01performance

Input{"_description":"n=1000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=1000 for s and p; O(m*n) DP solution must complete within 2 seconds.

💡 Use bottom-up DP with O(m*n) time complexity.

💡 Avoid exponential recursion without memoization.

💡 Optimize space if possible but prioritize time complexity.

Why it failed: TLE - naive exponential recursion causes timeout. Fix by implementing memoization or bottom-up DP with O(m*n) complexity.

✓ Efficient DP solution confirmed with O(m*n) complexity.

Practice

1. What is the time complexity of the space-optimized bottom-up DP solution for the Delete Operation for Two Strings problem, where the input strings have lengths m and n respectively?

medium

A. O(m * n)

B. O(m + n)

C. O(m * n * log(m + n))

D. O(m^2 + n^2)

Solution

1. Step 1: Identify nested loops over m and n

   The outer loop runs m times, inner loop runs n times, leading to m*n iterations.

2. Step 2: Confirm no extra hidden factors

   Each iteration does O(1) work; no sorting or recursion overhead.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP table size m*n and each cell computed once [OK]

Hint: Nested loops over m and n -> O(m*n) [OK]

Common Mistakes:

• Confusing linear with quadratic
• Assuming sorting or recursion adds log factor
• Ignoring nested loops

2. What is the time complexity of the space-optimized bottom-up DP solution for wildcard matching where m and n are the lengths of the input string and pattern respectively?

medium

A. O(m + n)

B. O(m * n)

C. O(2^(m + n))

D. O(m * n^2)

Solution

1. Step 1: Identify loops in the DP code

   The code has nested loops: outer loop runs m times, inner loop runs n times.

2. Step 2: Calculate total operations

   Each iteration does O(1) work, so total time is O(m * n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP fills a table of size m by n once [OK]

Hint: Nested loops over string and pattern lengths imply O(m*n) [OK]

Common Mistakes:

• Confusing with brute force exponential
• Assuming linear time
• Forgetting nested loops

3. What is the time complexity of the bottom-up DP solution for Word Break II that uses nested loops over the string and dictionary words, and concatenates sentences stored in dp arrays?

medium

A. O(n^3) due to nested loops and string concatenations

B. O(n^2 * m) because each substring is checked against dictionary words

C. O(2^n) because all segmentations are explored

D. O(n * m) where n = length of string, m = number of words in dictionary

Solution

1. Step 1: Identify nested loops and operations

   Outer loop runs n times, inner loop over dictionary words m times, and for each match, concatenation of strings from dp arrays occurs.

2. Step 2: Analyze concatenation cost

   Concatenation and copying sentences can cost up to O(n) each, and there can be O(n^2) substrings, leading to O(n^3) total time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Nested loops plus string concatenations cause cubic time [OK]

Hint: String concatenation inside nested loops causes O(n^3) [OK]

Common Mistakes:

• Confusing exponential brute force with DP complexity
• Ignoring concatenation cost

4. Suppose you want to count palindromic substrings in a string where characters can be replaced any number of times (reusable characters). Which modification to the expand around center approach correctly handles this variant?

hard

A. No modification needed; the original expand around center approach already counts palindromes with replacements.

B. Modify expand to allow skipping mismatched characters to find palindromes with replacements.

C. Precompute all possible character replacements and run the original expand around center for each variant.

D. Use dynamic programming with memoization to store counts for substrings allowing character replacements.

Solution

1. Step 1: Understand the variant

   Allowing character replacements means palindrome checks must consider substitutions, not exact matches.

2. Step 2: Evaluate approaches

   Expand around center relies on exact matches; skipping mismatches breaks palindrome definition. Precomputing all variants is exponential. DP with memoization can track allowed replacements efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP can handle flexible palindrome definitions with substitutions [OK]

Hint: Exact match expansion fails when replacements allowed [OK]

Common Mistakes:

• Assuming original approach works without changes

5. Suppose the problem is modified so that characters from s1 and s2 can be reused any number of times to form s3. Which of the following algorithmic changes correctly adapts the DP solution to this new requirement?

hard

A. Use the same DP but allow transitions to stay at the same indices in s1 or s2 when characters match, enabling reuse

B. No change needed; the original DP already handles reuse implicitly

C. Change the DP to a shortest path problem in a graph where edges represent character matches with reuse allowed

D. Modify the DP to consider infinite loops by adding a visited set to avoid cycles in recursion

Solution

1. Step 1: Understand reuse impact

   Allowing reuse means indices in s1 and s2 can stay the same or move forward, potentially causing cycles.

2. Step 2: Adapt algorithm

   To avoid infinite recursion or loops, the DP or recursion must track visited states to prevent cycles.

3. Step 3: Evaluate options

   Modify the DP to consider infinite loops by adding a visited set to avoid cycles in recursion correctly adds a visited set to recursion to handle cycles; others either do not prevent cycles or incorrectly claim no change is needed.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Cycle detection is essential when reuse is allowed to ensure termination [OK]

Hint: Reuse allows cycles; track visited states to avoid infinite loops [OK]

Common Mistakes:

• Assuming original DP handles reuse without modification
• Trying to model reuse with simple DP transitions without cycle checks