Regular Expression Matching

▶

Steps

setup

Initialize dp array

Create a dp array of size n+1 (pattern length + 1) initialized to False, then set dp[0] = True to represent empty string matching empty pattern.

💡 dp[0] = True means an empty string matches an empty pattern, which is the base case for the algorithm.

Line:

dp = [False] * (n + 1)
dp[0] = True

💡 The dp array tracks matching status for substrings of s against prefixes of p; starting with empty matches is essential.

setup

Pre-fill dp for patterns with '*'

Check pattern characters from index 2 to n to pre-fill dp[j] if p[j-1] is '*', setting dp[j] = dp[j-2]. Here pattern 'a' has length 1, so no '*' to process.

💡 Patterns with '*' can match empty strings by ignoring the preceding element, so dp is pre-filled accordingly.

Line:

for j in range(2, n + 1):
    if p[j - 1] == '*':
        dp[j] = dp[j - 2]

💡 This step prepares dp for patterns that can match empty strings, but here it leaves dp unchanged.

fill_row

Start processing first character of s (i=1, s[0]='a')

Begin processing the first character of the string 'a'. Save dp[0] in prev and set dp[0] = False since non-empty string cannot match empty pattern.

💡 dp[0] = False for i>0 because a non-empty string cannot match an empty pattern.

Line:

prev = dp[0]
dp[0] = False

💡 This step resets dp[0] for the current string prefix, preparing for pattern matching.

fill_cells

Check pattern character p[0] = 'a' against s[0] = 'a' (j=1)

For j=1, pattern character is 'a'. Since it is not '*', update dp[1] = prev and (p[0] == s[0]) which is True and True, so dp[1] = True.

💡 When pattern character is a normal character, dp[j] depends on previous dp[j-1] and character match.

Line:

temp = dp[1]
if p[j - 1] == '*':
    ...
else:
    dp[j] = prev and (p[j - 1] == '.' or p[j - 1] == s[i - 1])

💡 This shows how dp updates when pattern character matches string character directly.

fill_row

Finish processing i=1, dp array after first character

After processing s[0], dp array is [False, True], indicating s[:1] matches p[:1] but not empty pattern.

💡 dp array now shows which pattern prefixes match the first character of s.

Line:

for j in range(1, n + 1): ... (loop ends)

💡 The dp array correctly encodes partial matches after first character.

fill_row

Start processing second character of s (i=2, s[1]='a')

Begin processing second character of s. Save dp[0] in prev and set dp[0] = False since non-empty string cannot match empty pattern.

💡 Reset dp[0] for new string prefix length.

Line:

prev = dp[0]
dp[0] = False

💡 dp[0] always False for i>0, reflecting no match with empty pattern.

fill_cells

Check pattern character p[0] = 'a' against s[1] = 'a' (j=1)

For j=1, pattern character is 'a'. Update dp[1] = prev and (p[0] == s[1]) which is True and True, so dp[1] = True.

💡 Matching current characters updates dp accordingly.

Line:

temp = dp[1]
if p[j - 1] == '*':
    ...
else:
    dp[j] = prev and (p[j - 1] == '.' or p[j - 1] == s[i - 1])

💡 dp reflects that s[:2] matches p[:1] only if previous dp[0] was True and characters match.

fill_row

Finish processing i=2, dp array after second character

After processing s[1], dp array is [False, True], indicating s[:2] matches p[:1] only if dp[0] was True and characters matched.

💡 dp array shows partial matches after second character.

Line:

for j in range(1, n + 1): ... (loop ends)

💡 dp array remains unchanged, showing pattern 'a' matches only one character, not two.

reconstruct

Read final answer from dp[n]

Return dp[n], which is dp[1] = True, indicating s[:2] matches p[:1]. However, since s length is 2 and pattern length is 1, full match is false.

💡 dp[n] indicates if entire string matches entire pattern.

Line:

return dp[n]

💡 The algorithm returns False because pattern length < string length and no '*' to extend match.

reconstruct

Conclusion: Pattern does not match entire string

Since dp[n] does not confirm full match for entire string length, the function returns False, meaning pattern 'a' does not match string 'aa'.

💡 Final dp array state confirms no full match.

Line:

return dp[n]

💡 The dp array and final return value confirm the mismatch.

def isMatch(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    dp = [False] * (n + 1)  # STEP 1: Initialize dp array
    dp[0] = True  # STEP 1
    for j in range(2, n + 1):  # STEP 2: Pre-fill dp for '*'
        if p[j - 1] == '*':
            dp[j] = dp[j - 2]
    for i in range(1, m + 1):  # STEP 3: Iterate over s
        prev = dp[0]
        dp[0] = False  # STEP 3
        for j in range(1, n + 1):  # STEP 4: Iterate over p
            temp = dp[j]
            if p[j - 1] == '*':
                dp[j] = dp[j] or dp[j - 2]
                if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
                    dp[j] = dp[j] or prev
            else:
                dp[j] = prev and (p[j - 1] == '.' or p[j - 1] == s[i - 1])  # STEP 4
            prev = temp
    return dp[n]  # STEP 9 and 10

📊

Regular Expression Matching - Watch the Algorithm Execute, Step by Step

Watching each update to the dp array reveals how the algorithm incrementally builds the solution, making it easier to understand the role of '*' and '.' in pattern matching.

Item 0 - wt:0 val:0

i\w	0	1
i=0

dp[0] = True (empty matches empty)

Item 0 - wt:0 val:0

i\w	0	1
i=0

Item 0 - wt:0 val:0

i\w	0	1
i=0

dp[0] = False (non-empty s vs empty p)

Item 0 - wt:0 val:0

i\w	0	1
i=0

dp[1] = True (match 'a' with 'a')

Item 0 - wt:0 val:0

i\w	0	1
i=0

dp[1] = True

Item 1 - wt:0 val:0

i\w	0	1
i=0

dp[0] = False (non-empty s vs empty p)

Item 1 - wt:0 val:0

i\w	0	1
i=0

dp[1] = True (match 'a' with 'a')

Item 1 - wt:0 val:0

i\w	0	1
i=0

dp[1] = True

Item 1 - wt:0 val:0

i\w	0	1
i=0

Final dp[1] = True but string longer than pattern

Item 1 - wt:0 val:0

i\w	0	1
i=0

No full match: output False

Key Takeaways

✓ The dp array represents whether substrings of s match prefixes of p, building up from empty matches.

This insight is hard to see from code alone because dp updates are subtle and depend on previous states.

✓ Pattern characters '*' allow skipping or repeating previous elements, reflected by dp[j] depending on dp[j-2] and prev.

Visualizing dp updates clarifies how '*' affects matching possibilities.

✓ When pattern length is less than string length without '*', dp[n] cannot represent a full match, leading to false.

The trace shows concretely why partial matches do not imply full matches.

Practice

1. You are given two strings and need to find the shortest string that contains both as subsequences. Which algorithmic approach guarantees finding this shortest common supersequence efficiently?

easy

A. Greedy approach that merges characters from both strings whenever they differ

B. Dynamic programming based on longest common subsequence to build the shortest supersequence

C. Pure brute force recursion enumerating all supersequences and selecting the shortest

D. Sorting characters of both strings and merging them in lexicographical order

Solution

1. Step 1: Understand the problem requires minimal length supersequence containing both strings as subsequences

   Greedy or sorting approaches fail because they do not consider subsequence order constraints.

2. Step 2: Recognize that longest common subsequence (LCS) helps identify overlapping parts to minimize duplication

   Dynamic programming using LCS length allows building the shortest common supersequence efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   LCS-based DP is the classic and optimal approach for shortest common supersequence [OK]

Hint: Shortest common supersequence uses LCS-based DP [OK]

Common Mistakes:

• Thinking greedy merging always works
• Confusing substring with subsequence
• Assuming sorting helps

2. 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

3. The following code attempts to implement the space-optimized DP for longest common substring. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def longest_common_substring_space_optimized_buggy(s1, s2):
    n, m = len(s1), len(s2)
    dp = [0] * (m + 1)
    max_len = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):  # Note: iterating forward
            if s1[i - 1] == s2[j - 1]:
                dp[j] = dp[j - 1] + 1
                if dp[j] > max_len:
                    max_len = dp[j]
            else:
                dp[j] = 0
    return max_len

medium

A. Line with 'dp[j] = dp[j - 1] + 1' updating dp

B. Line with 'dp = [0] * (m + 1)' initializing dp array

C. Line with 'if dp[j] > max_len:' updating max_len

D. Line with 'for j in range(1, m + 1):' iterating forward

Solution

1. Step 1: Understand dp array update dependency

   dp[j] depends on dp[j-1] from previous iteration of inner loop, so iterating forward overwrites dp[j-1] before use.

2. Step 2: Identify iteration order bug

   Iterating j forward causes dp[j-1] to be updated before dp[j], corrupting the chain of matching lengths.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Changing inner loop to iterate backward fixes the bug [OK]

Hint: DP update depends on previous dp[j-1], so iterate backward [OK]

Common Mistakes:

• Updating dp forward overwrites needed values
• Incorrect max_len update timing
• Wrong dp initialization size

4. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the shortest common supersequence problem, where the input strings have lengths m and n?

medium

A. O(m * n)

B. O(m + n)

C. O(m * n * min(m, n))

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

Solution

1. Step 1: Identify nested loops over m and n in the DP code

   The outer loop runs m times, inner loop runs n times, each iteration constant work.

2. Step 2: Confirm no extra multiplicative factors from recursion or auxiliary structures

   Space optimization reduces space but does not affect time complexity, which remains O(m*n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP table filling requires m*n steps, no hidden extra loops [OK]

Hint: DP with two nested loops over m and n -> O(m*n) time [OK]

Common Mistakes:

• Confusing space with time complexity
• Assuming recursion stack adds multiplicative factor
• Thinking linear time is possible

5. Suppose you want to find the longest palindromic substring in a string where characters can be added or removed dynamically, and you need to support queries efficiently. Which approach is best suited to handle this follow-up?

hard

A. Use the same DP tabulation approach on the entire string for each query

B. Use a suffix tree or suffix automaton to find palindromic substrings efficiently

C. Use Manacher's algorithm combined with segment trees or balanced BSTs for dynamic updates

D. Use brute force palindrome checks for each query since updates are rare

Solution

1. Step 1: Understand dynamic updates requirement

   DP tabulation recomputes entire table O(n^2) per query, inefficient for dynamic changes.

2. Step 2: Identify suitable data structures

   Manacher's algorithm finds longest palindrome in O(n), but not dynamic. Combining it with segment trees or balanced BSTs allows efficient updates and queries.

3. Step 3: Evaluate other options

   Suffix trees/automata help substring queries but not specifically palindromes with dynamic updates. Brute force is too slow.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Dynamic palindrome queries require advanced data structures [OK]

Hint: Dynamic palindrome queries need specialized data structures [OK]

Common Mistakes:

• Re-running DP for each query
• Using suffix trees without palindrome focus
• Ignoring update complexity