Understanding Substring Search

When we talk about substring search, we're generally referring to the task of finding a specific pattern within a larger string. This becomes more interesting when we introduce wildcards, which are special characters that can represent one or more characters in a string. The most common wildcard characters are ?, which matches any single character, and *, which matches any sequence of characters (including an empty sequence).

Examples of Wildcards

1. ? Wildcard:

   • Pattern: h?llo
   • Matches: hello, hallo, h3llo
   • Does not match: hlllo

2. * Wildcard:

   • Pattern: h*llo
   • Matches: hello, helloo, hworldllo, hlllo
   • Does not match: (none, because * can be empty)

3. Combination:

   • Pattern: h*llo?
   • Matches: helloX, helloo5, hworldlloZ
   • Does not match: hlllo, hello

Why Use Wildcards?

Wildcards allow for more flexible searching compared to fixed patterns, which is particularly useful in situations where the exact content may vary but the structure remains constant. A common real-world example is searching through a database of usernames or files where you may not remember the exact name but only parts of it.

Algorithms for Substring Search with Wildcards

1. Naive Approach

The simplest way to handle substring searching with wildcards is the naive approach. This is straightforward but inefficient for larger strings. Here’s how it works:

• For each position in the main string, check if the substring starting at that position matches the pattern:
  • If the character in the pattern is a *, skip through all matching characters.
  • If the character is a ? or matches the character in the string, proceed.
  • If a mismatch occurs, go to the next position in the string.

Complexity: O(n * m) in the worst case, where n is the length of the main string and m is the length of the pattern.

Example Implementation of Naive Approach

def wildcard_match(s, p):
    def match(i, j):
        if j == len(p):
            return i == len(s)
        if i < len(s) and (p[j] == s[i] or p[j] == '?'):
            return match(i + 1, j + 1)
        if p[j] == '*':
            return match(i, j + 1) or (i < len(s) and match(i + 1, j))
        return False

    return match(0, 0)

2. Dynamic Programming Approach

A more efficient method to handle wildcard substring search is by utilizing dynamic programming. The idea is to build a 2D table where the cell dp[i][j] signifies whether the first i characters in the string s match the first j characters in the pattern p.

Steps to Implement:

1. Create a 2D DP table of size (n+1) x (m+1) initialized to False.
2. Set dp[0][0] to True (empty pattern matches empty string).
3. Fill the first row for patterns starting with * that can match an empty string.
4. Iterate through each character of the string and pattern:
   • If they match, carry forward the previous match.
   • If the pattern character is a ?, carry forward as well.
   • If the pattern character is *, consider both scenarios: matching one-less character or using the * to match multiple characters.

Complexity: O(n * m)

Example Implementation Using Dynamic Programming

def wildcard_match_dp(s, p):
    n, m = len(s), len(p)
    dp = [[False] * (m + 1) for _ in range(n + 1)]
    dp[0][0] = True

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

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if p[j - 1] == '*':
                dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
            elif p[j - 1] == s[i - 1] or p[j - 1] == '?':
                dp[i][j] = dp[i - 1][j - 1]

    return dp[n][m]

Applications of Substring Search with Wildcards

Understanding and implementing substring search algorithms that support wildcards plays a crucial role in various fields, including:

• Database Searching: Efficiently locating records with flexible matching criteria.
• Text Editors: Features like “find” that allow users to search with wildcards.
• Search Engines: Algorithms used to optimize search queries with ambiguous terms.

Staying equipped with these substring search methods will not only prepare you for coding interviews but also enhance your problem-solving toolkit for real-world applications.