Wildcard Matching

📋

Wildcard Matching

Edge cases:

</>

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
    return false;
}

Common Bugs to Avoid

Wrong: true for s='aa', p='a'Returning true if pattern matches prefix only, not entire string✅ Ensure full string length is matched by pattern; check indices reach end of both s and p

Wrong: false for s='', p='*'Not treating '*' as matching empty sequence in base case✅ Initialize dp so that pattern of all '*' matches empty string

Wrong: false for s='abcde', p='a*de'Greedy '*' matching too early without exploring all expansions✅ Use DP to explore all '*' expansions instead of greedy first match

Wrong: false for s='aaa', p='*a'Treating '*' as matching only zero or one character instead of unbounded✅ Allow '*' to match zero or more characters in dp recurrence

Wrong: false for s='abc', p='a?c'Off-by-one indexing error when matching '?'✅ Increment indices correctly when matching '?' in dp

✓

Test Cases

Try testing your solution on empty strings and single character patterns.

Consider tricky cases where greedy matching fails or indexing errors occur.

Optimize your solution to avoid exponential time complexity.

t1_01basic

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

Expectedfalse

⏱ Performance - must finish in 2000ms

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

💡 Consider how each character in pattern matches characters in string

💡 Check if pattern length matches string length when no '*' present

💡 Return false if pattern shorter than string and no '*' to cover extra chars

Why it failed: Incorrectly returned true or partial match; fix by ensuring full string must be matched by pattern, not prefix only. This is the canonical basic case.

✓ Correctly identified that pattern 'a' does not match string 'aa'.

t1_02basic

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

Expectedtrue

⏱ Performance - must finish in 2000ms

'*a*b' matches 'adceb' because '*' matches 'adc', 'a' matches 'a', '*' matches 'e', and 'b' matches 'b'

💡 Remember '*' can match any sequence including empty

💡 Try dynamic programming to track matches up to each index

💡 Use dp[i][j] = dp[i][j-1] or dp[i-1][j] when pattern[j] is '*'

Why it failed: Failed to handle '*' matching multiple characters; fix by allowing '*' to match zero or more characters using dp recurrence. This is a core basic case.

✓ Correctly handled '*' wildcard matching multiple characters.

t2_01edge

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

Expectedtrue

⏱ Performance - must finish in 2000ms

Pattern '*' matches empty string

💡 Check how '*' matches empty sequences

💡 Initialize dp for empty string and pattern with '*' correctly

💡 Return true if pattern is all '*' and string is empty

Why it failed: Returned false for empty string with '*' pattern; fix by treating '*' as matching empty sequence in base cases. This is the empty input edge case.

✓ Correctly matched empty string with '*' pattern.

t2_02edge

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

Expectedtrue

⏱ Performance - must finish in 2000ms

'?' matches exactly one character, so matches 'a'

💡 Check how '?' matches exactly one character

💡 Ensure pattern and string lengths match when only '?' present

💡 Return true if all pattern chars are '?' and lengths equal

Why it failed: Returned false for single character match with '?'; fix by allowing '?' to match any single character. This is the single element edge case.

✓ Correctly matched single character string with '?' pattern.

t2_03edge

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

Expectedtrue

⏱ Performance - must finish in 2000ms

'abc*' matches 'abc' because '*' can match empty sequence

💡 Check if trailing '*' can match empty sequence

💡 Ensure dp handles pattern longer than string with trailing '*' correctly

💡 Return true if remaining pattern chars are all '*' after matching string

Why it failed: Returned false when pattern longer than string but trailing '*' present; fix by allowing trailing '*' to match empty sequence. This is the exact boundary edge case.

✓ Correctly matched string with pattern longer due to trailing '*'.

t2_04edge

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

Expectedtrue

⏱ Performance - must finish in 2000ms

Pattern with only '?' matches string if lengths are equal

💡 Check that '?' matches exactly one character

💡 Verify pattern and string lengths are equal

💡 Return true if all pattern chars are '?' and lengths match

Why it failed: Returned false for pattern with only '?' matching string of equal length; fix by ensuring '?' matches exactly one character. This is the all '?' identical pattern edge case.

✓ Correctly matched string with pattern of all '?'.

t3_01corner

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

Expectedtrue

⏱ Performance - must finish in 2000ms

'a*de' matches 'abcde' because '*' can match 'bc'

💡 Beware greedy matching '*' too early

💡 Check all possible expansions of '*' instead of greedy first match

💡 Use dp to explore all '*' expansions rather than greedy

Why it failed: Incorrectly returned false due to greedy '*' matching; fix by exploring all '*' expansions with dp instead of greedy. This is the greedy trap corner case.

✓ Correctly avoided greedy trap and returned true.

t3_02corner

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

Expectedtrue

⏱ Performance - must finish in 2000ms

'*a' matches 'aaa' because '*' matches 'aa' and 'a' matches last 'a'

💡 Distinguish between 0/1 and unbounded '*' matches

💡 Allow '*' to match multiple characters, not just one

💡 Use dp recurrence dp[i][j] = dp[i][j-1] or dp[i-1][j] for '*'

Why it failed: Failed to allow '*' to match multiple characters; fix by allowing '*' to match zero or more characters in dp. This is the 0/1 vs unbounded confusion test.

✓ Correctly handled '*' matching multiple characters.

t3_03corner

Input{"s":"abc","p":"a?c"}

Expectedtrue

⏱ Performance - must finish in 2000ms

'a?c' matches 'abc' because '?' matches 'b'

💡 Check off-by-one errors in indexing string and pattern

💡 Ensure indices increment correctly when matching '?'

💡 Verify dp transitions handle '?' correctly

Why it failed: Returned false due to off-by-one indexing error; fix by correctly incrementing indices when matching '?'. This is the off-by-one corner case.

✓ Correctly handled '?' matching with proper indexing.

t4_01performance

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

Expectednull

⏱ Performance - must finish in 2000ms

n=100, pattern and string length 100, O(m*n) DP must complete within 2s

💡 Use dynamic programming with memoization or tabulation

💡 Avoid exponential recursion by caching results

💡 Optimize space by using rolling arrays if possible

Why it failed: TLE due to exponential brute force recursion; fix by implementing O(m*n) DP with memoization or tabulation. This is the performance complexity test.

✓ Efficient O(m*n) DP solution confirmed by passing performance test.

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

3. Examine the following buggy code for shortest common supersequence length. Which line contains the subtle bug that causes incorrect results when one input string is empty?

medium

A. Line 7: Condition comparing str1[i-1] and str2[j-1]

B. Line 5: Initialization of curr with [i] + [0]*n

C. Line 10: Updating prev = curr

D. Line 3: Initialization of prev with zeros instead of range

Solution

1. Step 1: Check base case initialization of prev array

   Prev should be initialized as range(n+1) to represent base case when str1 is empty; zeros cause incorrect base lengths.

2. Step 2: Confirm other lines correctly implement DP transitions

   Lines initializing curr, comparing characters, and updating prev are correct.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Incorrect base initialization leads to wrong results when one string is empty [OK]

Hint: Base case initialization must reflect empty string lengths [OK]

Common Mistakes:

• Initializing dp arrays with zeros instead of incremental ranges
• Mixing up indices in conditions
• Forgetting to update prev array

4. Suppose you want to find the length of the longest common subsequence between two strings, but now characters from the second string can be reused multiple times. Which modification to the standard LCS algorithm correctly handles this scenario?

hard

A. Use the same DP but allow dp[j] to depend on dp[j] itself without decrementing j in inner loop

B. Change the inner loop to iterate forwards and update dp[j] using dp[j] and dp[j-1] to allow reuse

C. Use a greedy approach matching characters from left to right allowing reuse

D. Use a bottom-up DP with a 2D table but ignore previous matches to allow reuse

Solution

1. Step 1: Understand reuse impact

   Allowing reuse of characters in the second string means dp[j] can be updated based on dp[j] itself (not only dp[j-1]) and the inner loop must run forwards to propagate reuse correctly.

2. Step 2: Identify correct DP iteration

   Iterating forwards in the inner loop allows dp[j] to accumulate matches with reuse, unlike standard LCS which iterates backwards to avoid reuse.

3. Step 3: Evaluate other options

   Greedy fails to find optimal subsequence. Ignoring previous matches breaks DP correctness. Using 2D DP without reuse logic is insufficient.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Forward iteration in inner loop enables reuse of characters [OK]

Hint: Forward inner loop iteration enables reuse in DP [OK]

Common Mistakes:

• Using backward iteration preventing reuse
• Trying greedy approach
• Ignoring DP state dependencies

5. Suppose you want to find the shortest common supersequence when characters from the input strings can be reused unlimited times. Which modification to the DP approach correctly handles this variant?

hard

A. Change the recurrence to allow staying at the same index in one string while advancing in the other

B. Modify the DP to consider infinite loops by adding memoization to avoid repeated states

C. Use the same DP but allow indices i and j to reset to zero after reaching the end, enabling reuse

D. No change needed; the original DP already accounts for unlimited reuse of characters

Solution

1. Step 1: Understand that unlimited reuse means characters can be used multiple times, so indices may not always advance

   Original DP always advances both indices or one index forward, disallowing reuse.

2. Step 2: Modify recurrence to allow staying at the same index in one string while advancing in the other

   This models reuse by allowing repeated characters from one string to be matched multiple times.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Allowing index to stay while advancing the other correctly models reuse [OK]

Hint: Reuse means indices may not always advance simultaneously [OK]

Common Mistakes:

• Assuming original DP handles reuse
• Trying to reset indices naively
• Adding memoization without changing recurrence