Wildcard Matching

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True

        # Handle patterns with '*' at the start
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 1]

        # Iterate through the string and pattern
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                    dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
                elif p[j - 1] == '?' or p[j - 1] == s[i - 1]:
                    dp[i][j] = dp[i - 1][j - 1]

        return dp[m][n]

This function uses dynamic programming (a 2D table dp) to handle the various cases of pattern matching. It iterates through the string s and the pattern p, and fills the table based on the current characters.

  • If the current pattern character is a *, it means it can match zero or more occurrences, so the value is derived from the previous row or column.
  • If the current pattern character is a ? or matches the current string character, the value is derived from the top-left diagonal.

Finally, the value at dp[m][n] tells whether the entire pattern matches the entire string.

Identifying Problem Isomorphism

“Wildcard Matching” has an approximate isomorph: “Regular Expression Matching”

In “Wildcard Matching”, you’re given an input string (s) and a pattern (p), where the pattern may include the wildcard characters ‘?’ and ‘’. ‘?’ matches any single character, and ‘’ matches any sequence of characters (including an empty sequence). The task is to implement wildcard pattern matching with support for ‘?’ and ‘*’.

In “Regular Expression Matching”, you’re also given an input string (s) and a pattern (p). The pattern can contain the special characters ‘.’ and ‘’. ‘.’ Matches any single character, and ‘’ Matches zero or more of the preceding element. The task is to implement support for ‘.’ and ‘*’ in a regular expression.

The similarity between them is the concept of pattern matching with wildcards, with ‘?’ and ‘’ in “Wildcard Matching” behaving similarly to ‘.’ and ‘’ in “Regular Expression Matching”.

While both problems deal with matching patterns to a given string, “Regular Expression Matching” is more complex due to the nature of regular expressions. “Wildcard Matching” is simpler, mainly dealing with wildcard characters in a straightforward manner.

10 Prerequisite LeetCode Problems

The “Wildcard Matching” involves understanding of string matching, dynamic programming, and recursion. Here are 10 problems to prepare:

  1. “Valid Anagram” (LeetCode Problem #242): This problem introduces the basic concept of character manipulation and comparison in strings.

  2. “Longest Common Prefix” (LeetCode Problem #14): This problem will teach you how to find common patterns across multiple strings.

  3. “Implement strStr()” (LeetCode Problem #28): This problem provides practice on basic string matching.

  4. “Palindrome Partitioning” (LeetCode Problem #131): It helps you understand how to handle multiple possibilities in string processing.

  5. “Subsets” (LeetCode Problem #78): You will learn how to generate and manipulate different sets, which is a concept used in matching patterns.

  6. “Permutations” (LeetCode Problem #46): This problem will make you comfortable with recursion which is a common approach to solve pattern matching problems.

  7. “Regular Expression Matching” (LeetCode Problem #10): This problem is a simpler version of wildcard matching and will help you understand the basics of pattern matching with special characters.

  8. “Partition Equal Subset Sum” (LeetCode Problem #416): It will help you understand dynamic programming, a common technique used in wildcard matching.

  9. “Unique Paths” (LeetCode Problem #62): This problem introduces the basic concept of dynamic programming, and can be solved using a similar approach as wildcard matching.

  10. “Decode Ways” (LeetCode Problem #91): This problem requires you to find all possible interpretations of a string, a similar concept to finding all matches in wildcard matching.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        i = 0
        j = 0

        last_match = 0
        star = -1

        while i < len(s):
            if j < len(p) and (s[i] == p[j] or p[j] == '?'):
                i += 1
                j += 1

            elif j < len(p) and p[j] == '*':
                last_match = i
                star = j
                j += 1

            elif star != -1:
                j = star + 1
                i = last_match + 1
                last_match += 1
            else:
                return False

        while j < len(p) and p[j] == '*':
            j += 1

        return j == len(p)

Problem Classification

This problem involves determining if a string matches a pattern that can contain wildcard characters. It’s a type of pattern recognition problem hence the classification Pattern Matching.

Language Agnostic Coding Drills

The solution for a wildcard matching problem, checks if the input string s matches the pattern p. The pattern may contain literal characters and two special characters: * (matches any sequence of characters, including an empty one) and ? (matches exactly one arbitrary character).

Here are the key concepts involved in the code, arranged in order of difficulty:

  1. Working with strings: Understanding how to manipulate, access, and compare strings.

  2. Iterating through strings: Understand how to use loops to iterate over each character in a string.

  3. Understanding conditional statements: Using if-else conditions to check for different cases while matching the string with the pattern.

  4. Comparison of characters: Comparing each character of the string and pattern.

  5. Working with wildcard characters: Handling special characters like * and ?.

  6. Maintaining state information: Keeping track of the position of certain special characters or matches.

  7. Nested loops: The use of multiple while loops, some of them nested, for the string matching operation.

  8. Backtracking: The code utilizes a form of backtracking in order to revisit previous matching points when it encounters a special character *.

The problem-solving approach:

  1. Loop over the string s and compare each character to the corresponding character in the pattern p.

  2. If the characters match or the pattern has a ?, move to the next characters.

  3. If the pattern has a *, store the current position in the string and the position after the * in the pattern. Move to the next character in the pattern.

  4. If there is no match, but we have encountered a * before, then backtrack to the position after the * in the pattern, and move to the next character in the string from the last matching position.

  5. If there is no match and no * to backtrack to, return False as the string does not match the pattern.

  6. After the loop, if there are any remaining * in the pattern, skip them. If we reach the end of the pattern, return True as the string matches the pattern.

Targeted Drills in Python

  1. Working with strings:

    • Create a string, access its characters by index, find its length and concatenate two strings.
    1
2
3
4
5
6
7
8
9

    # create a string
s = "Hello, World!"
# access characters
print(s[0])  # prints 'H'
# string length
print(len(s))  # prints 13
# string concatenation
s2 = " How are you?"
print(s + s2)  # prints "Hello, World! How are you?"

  2. Iterating through strings:

    • Use a for loop to iterate over each character in a string.
    1
2
3

    s = "Hello, World!"
for character in s:
    print(character)

  3. Understanding conditional statements:

    • Write a simple if-else condition to compare two numbers.
    1
2
3
4
5
6

    a = 5
b = 10
if a < b:
    print("a is less than b")
else:
    print("a is not less than b")

  4. Comparison of characters:

    • Compare two characters.
    1
2
3
4
5
6

    char1 = 'a'
char2 = 'b'
if char1 == char2:
    print('Characters are the same')
else:
    print('Characters are different')

  5. Working with wildcard characters:

    • Compare characters considering ‘?’ as a wildcard.
    1
2
3
4
5
6

    char1 = '?'
char2 = 'b'
if char1 == '?' or char2 == '?' or char1 == char2:
    print('Match')
else:
    print('No match')

  6. Maintaining state information:

    • Keep track of the position of certain special characters or matches.
    1
2
3
4

    s = "Hello, World!"
# keep track of the position of 'o'
positions = [i for i, char in enumerate(s) if char == 'o']
print(positions)  # prints [4, 8]

  7. Nested loops:

    • Write a simple program with nested loops.
    1
2
3

    for i in range(3):
    for j in range(3):
        print(i, j)

  8. Backtracking:

    • Create a simple recursive function to demonstrate backtracking (e.g., generating all binary strings of length n).
    1
2
3
4
5
6
7
8

    def generate_binary(n, result=''):
    if len(result) == n:
        print(result)
        return
    generate_binary(n, result + '0')
    generate_binary(n, result + '1')

generate_binary(3)  # prints all binary strings of length 3

The drills provided above should assist in understanding the components of the code snippet. By working through each one, you should gain a good grasp of the fundamental concepts utilized in the problem.