Wildcard Matching

▶

Steps

setup

Initialize lengths and DP arrays

We determine the lengths of the string and pattern, then initialize the 'prev' array with False values except prev[0] which is True, representing empty string and empty pattern match.

💡 Setting prev[0] to True establishes the base case: empty pattern matches empty string.

Line:

m, n = len(s), len(p)
prev = [False] * (n + 1)
prev[0] = True

💡 Base case initialization is essential for building the DP solution from the ground up.

setup

Pre-fill prev for pattern '*' matching empty string

We check if the pattern starts with '*' characters and update prev accordingly to reflect that '*' can match empty string prefixes.

💡 This step handles patterns that can match empty strings by using '*' wildcard, which can represent zero characters.

Line:

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

💡 Since pattern does not start with '*', only prev[0] remains True, others stay False.

fill_row

Start outer loop: i=1 (first character of s)

We begin processing the first character of the string 's' (which is 'a'), initializing a new 'curr' array for this row with all False values.

💡 Each iteration over the string builds a new DP row representing matches up to that character.

Line:

for i in range(1, m + 1):
    curr = [False] * (n + 1)

💡 A fresh 'curr' array is needed to compute matches for the current prefix of the string.

fill_cells

Set curr[0] = False for i=1

We explicitly set curr[0] to False because a non-empty string cannot match an empty pattern.

💡 This boundary condition is important: pattern empty means no match unless string is also empty.

Line:

curr = [False] * (n + 1)

💡 This enforces that empty pattern matches only empty string.

fill_cells

Inner loop j=1: pattern char 'a' vs string char 'a'

We compare pattern character 'a' with string character 'a'. Since they match, curr[1] is set to prev[0], which is True.

💡 Matching characters means the result depends on whether previous prefixes matched.

Line:

if p[j - 1] == '?' or p[j - 1] == s[i - 1]:
    curr[j] = prev[j - 1]

💡 This shows how matching characters propagate True values diagonally in the DP table.

fill_row

End of inner loop for i=1, swap prev and curr

We finish processing the first string character and assign curr to prev for the next iteration.

💡 Swapping arrays allows us to reuse space and move to the next string prefix.

Line:

prev = curr

💡 The DP arrays now represent matches up to s[:1].

fill_row

Start outer loop: i=2 (second character of s)

We begin processing the second character of the string 's' (which is also 'a'), initializing a new 'curr' array with all False values.

💡 Each new string character requires a fresh DP row to compute matches.

Line:

for i in range(1, m + 1):
    curr = [False] * (n + 1)

💡 We prepare to compute matches for s[:2].

fill_cells

Set curr[0] = False for i=2

We set curr[0] to False because a non-empty string prefix cannot match an empty pattern.

💡 This boundary condition remains consistent for all string prefixes.

Line:

curr = [False] * (n + 1)

💡 Empty pattern cannot match non-empty string prefix.

fill_cells

Inner loop j=1: pattern char 'a' vs string char 'a' (second char)

We compare pattern character 'a' with string character 'a'. They match, so curr[1] is set to prev[0], which is False this time.

💡 Matching characters depend on previous diagonal cell in DP table.

Line:

if p[j - 1] == '?' or p[j - 1] == s[i - 1]:
    curr[j] = prev[j - 1]

💡 Even matching characters can fail if previous prefixes did not match.

fill_row

End of inner loop for i=2, swap prev and curr

We finish processing the second string character and assign curr to prev for the next iteration (if any).

💡 Swapping arrays updates DP state to reflect matches up to s[:2].

Line:

prev = curr

💡 The DP arrays now represent matches up to the full string.

reconstruct

Read final answer from prev[n]

We check the last cell prev[n] which indicates if the entire string matches the entire pattern. It is False, so the pattern does not match the string.

💡 The final DP cell gives the answer to the matching problem.

Line:

return prev[n]

💡 The DP table confirms that pattern 'a' does not match string 'aa'.

def isMatch(s: str, p: str) -> bool:
    m, n = len(s), len(p)  # STEP 1
    prev = [False] * (n + 1)  # STEP 1
    prev[0] = True  # STEP 1
    for j in range(1, n + 1):  # STEP 2
        if p[j - 1] == '*':  # STEP 2
            prev[j] = prev[j - 1]  # STEP 2
    for i in range(1, m + 1):  # STEP 3
        curr = [False] * (n + 1)  # STEP 3
        for j in range(1, n + 1):  # STEP 5 & 9
            if p[j - 1] == '*':  # Not used in this example
                curr[j] = curr[j - 1] or prev[j]
            elif p[j - 1] == '?' or p[j - 1] == s[i - 1]:  # STEP 5 & 9
                curr[j] = prev[j - 1]
        prev = curr  # STEP 6 & 10
    return prev[n]  # STEP 11

📊

Wildcard Matching - Watch the Algorithm Execute, Step by Step

Watching this visualization helps you understand how the algorithm uses previous computations to build up the solution efficiently, especially how '*' and '?' wildcards affect matching.

Item 0 - wt:0 val:0

i\w	0	1
i=0

prev[0] = True (empty matches empty)

Item 0 - wt:0 val:0

i\w	0	1
i=0

prev[0] = True

Item 0 - wt:0 val:0

i\w	0	1
i=0
i=1

curr[0] = False initially

Item 0 - wt:0 val:0

i\w	0	1
i=0
i=1

curr[0] = False (non-empty string vs empty pattern)

Item 0 - wt:0 val:0

i\w	0	1
i=0
i=1

curr[1] = True (match 'a' == 'a')

Item 0 - wt:0 val:0

i\w	0	1
i=0
i=1

prev updated to curr

Item 1 - wt:0 val:0

i\w	0	1
i=0
i=1
i=2

curr[0] = False initially

Item 1 - wt:0 val:0

i\w	0	1
i=0
i=1
i=2

curr[0] = False

Item 1 - wt:0 val:0

i\w	0	1
i=0
i=1
i=2

curr[1] = False (prev[0] = False)

Item 1 - wt:0 val:0

i\w	0	1
i=0
i=1
i=2

prev updated to curr

Item 1 - wt:0 val:0

i\w	0	1
i=0
i=1
i=2

Answer cell: False

Key Takeaways

✓ The DP arrays 'prev' and 'curr' efficiently represent matches for prefixes of the string and pattern, enabling space optimization.

This insight is hard to see from code alone because the arrays are 1D and reused, but the visualization shows the full 2D DP table concept.

✓ Exact character matches propagate True values diagonally in the DP table, reflecting prefix matches.

Seeing the diagonal dependency visually clarifies how matching characters influence the DP state.

✓ Even if characters match, the overall match can fail if previous prefixes did not match, as shown when curr[1] becomes False for the second 'a'.

This concrete example shows why the DP table must be fully computed and not just rely on single character comparisons.

Practice

1. You are given three strings s1, s2, and s3. Determine if s3 can be formed by interleaving the characters of s1 and s2 while preserving the order of characters in each string. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Pure brute force recursion without memoization to explore all character combinations

B. Greedy algorithm that picks characters from s1 or s2 whenever they match s3 sequentially

C. Dynamic Programming using a 2D table to track interleaving possibilities for prefixes of s1 and s2

D. Sorting all strings and then comparing if s3 is a merged sorted string of s1 and s2

Solution

1. Step 1: Understand problem constraints

   The problem requires preserving the order of characters from both s1 and s2 to form s3. This rules out greedy and sorting approaches.

2. Step 2: Identify suitable algorithm

   Dynamic Programming with a 2D table tracks whether prefixes of s1 and s2 can form prefixes of s3, guaranteeing an optimal solution.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP ensures all prefix combinations are checked systematically [OK]

Hint: Interleaving requires DP to track prefix matches [OK]

Common Mistakes:

• Assuming greedy works because characters match sequentially
• Thinking sorting helps preserve order

2. What is the time complexity of the optimal space-optimized dynamic programming solution for counting distinct subsequences of t in s, where m = len(s) and n = len(t)?

medium

A. O(m + n)

B. O(2^m)

C. O(m * n)

D. O(m * n^2)

Solution

1. Step 1: Identify nested loops over s and t

   The code iterates over all characters of s (m times) and for each, iterates over t (n times) in reverse order.

2. Step 2: Calculate total operations

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

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two nested loops over lengths m and n -> O(m*n) [OK]

Hint: Nested loops over s and t imply O(m*n) time [OK]

Common Mistakes:

• Confusing recursion exponential time with DP time
• Ignoring nested loop structure

3. What is the time complexity of the optimal palindrome partitioning min cuts algorithm that uses a 1D dp array with palindrome center expansion?

medium

A. O(n) because each character is processed once

B. O(n^2) because palindrome expansions around each center take quadratic time

C. O(n^3) due to nested loops and substring palindrome checks

D. O(n log n) due to binary search on palindrome substrings

Solution

1. Step 1: Identify palindrome center expansions

   For each of the n centers, expansions can take up to O(n) time in worst case.

2. Step 2: Calculate total time complexity

   Since there are n centers and each can expand up to n, total time is O(n^2). No substring slicing or extra nested loops increase complexity beyond quadratic.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Quadratic time matches palindrome center expansion approach [OK]

Hint: Palindrome expansions around centers lead to O(n^2) time [OK]

Common Mistakes:

• Assuming linear time due to single loop
• Confusing with cubic time from naive substring checks
• Thinking binary search applies here

4. The following code attempts to implement space-optimized DP for regex matching. Which line contains a subtle bug that causes incorrect results on some inputs?

def isMatch(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    dp = [False] * (n + 1)
    dp[0] = True
    for j in range(2, n + 1):
        if p[j - 1] == '*':
            dp[j] = dp[j - 2]
    for i in range(1, m + 1):
        prev = dp[0]
        dp[0] = False
        for j in range(1, n + 1):
            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])
            prev = temp
    return dp[n]

medium

A. Line: dp[0] = False inside the outer loop

B. Line: for j in range(1, n + 1): iterating forwards instead of backwards

C. Line: prev = dp[0] before inner loop starts

D. Line: dp[j] = dp[j] or dp[j - 2] inside the '*' handling block

Solution

1. Step 1: Understand dp array update dependencies

   When updating dp[j], dp[j - 2] must not be overwritten before use. Iterating forwards overwrites dp[j - 2] too early.

2. Step 2: Identify iteration direction bug

   Iterating forwards causes dp[j - 2] to be stale or overwritten, leading to incorrect matches. Iterating backwards avoids this.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Known bug in space-optimized regex DP is forward iteration [OK]

Hint: DP updates with '*' require backward iteration to preserve dp[j-2] [OK]

Common Mistakes:

• Assuming forward iteration is safe in space-optimized DP

5. Suppose the problem is modified so that each integer in nums1 and nums2 can be used multiple times to form uncrossed lines (i.e., reuse allowed). Which of the following algorithmic changes correctly adapts the solution?

hard

A. Modify the DP to consider unlimited reuse by allowing transitions that do not increment both indices simultaneously after a match

B. Change the DP to allow staying on the same index in nums1 or nums2 after a match, effectively converting to a longest common substring problem

C. Use a greedy approach to connect all matching pairs regardless of crossing

D. Use the same DP but allow matching the same indices multiple times by removing the increment of i and j after a match

Solution

1. Step 1: Understand reuse implications

   Allowing reuse means after matching nums1[i] and nums2[j], we can match nums1[i] or nums2[j] again, so indices may not both increment.

2. Step 2: Adapt DP transitions

   The DP must allow transitions that increment only one index or none after a match, unlike classic LCS where both indices increment. This requires modifying the recurrence to consider reuse.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Allowing reuse requires DP transitions that do not always increment both indices [OK]

Hint: Reuse means indices may not both advance after a match [OK]

Common Mistakes:

• Removing increments without adjusting DP
• Confusing reuse with substring problem
• Using greedy approach ignoring crossing