Substring Matching Pattern - Solution & Explanation

Problem Overview: You are given a text string s and a pattern p. The pattern contains lowercase characters and a wildcard * that can match any sequence of characters (including empty). The task is to determine whether some substring of s matches the pattern.

Approach 1: Brute Force Substring Check (O(n^3) time, O(1) space)

Generate every possible substring of s using two nested loops for the start and end index. For each substring, check whether it matches the pattern by simulating the wildcard behavior. When the pattern contains *, split it logically and test whether the substring starts with the prefix and ends with the suffix. This approach is easy to reason about but inefficient because substring generation is O(n^2) and each comparison may take up to O(n). It works only for very small inputs but helps you understand the structure of the problem.

Approach 2: Prefix–Suffix String Matching (O(n) time, O(1) space)

The key observation is that the pattern contains a wildcard that can represent any sequence. Split the pattern around * into two parts: prefix and suffix. A valid substring must start with prefix and later end with suffix. Scan the string to find occurrences of the prefix, then check whether the suffix appears at or after the position where the prefix match ends. Because each scan is linear, the total runtime stays O(n). This method relies purely on string operations such as substring comparison and index scanning.

Implementation typically checks edge cases first. If the prefix is empty, only the suffix must appear somewhere in the string. If the suffix is empty, only the prefix must appear. Otherwise, iterate through the string and compare characters to confirm the prefix match, then verify the suffix occurs later. This approach is simple, cache-friendly, and performs well in interviews and production code.

Approach 3: String Matching with KMP (O(n + m) time, O(m) space)

For very large inputs or repeated queries, you can use a classic string matching algorithm such as KMP. First search for all occurrences of the prefix using KMP preprocessing. Then search for suffix occurrences and ensure at least one suffix appears after a prefix match. KMP avoids repeated character comparisons and guarantees linear time relative to the text and pattern length.

Recommended for interviews: The prefix–suffix scan is the expected solution. It demonstrates that you recognized the wildcard structure and reduced the problem to simple string comparisons. Mentioning the brute force approach shows baseline reasoning, but implementing the linear scan proves you can optimize string matching problems efficiently.