LeetCode Problem 3407

Difficulty: 🟢 Easy
Topics: String, String Matching

Solution

LeetCode 3407. Substring Matching Pattern

Problem Understanding

The problem gives us two strings:

• s, the source string.
• p, a pattern string containing exactly one '*'.

The special character '*' can represent any sequence of characters, including an empty sequence. The goal is to determine whether there exists some substring of s that can match the pattern after replacing '*' with an arbitrary string.

It is important to notice that we are not matching the entire string s. We only need to find a substring of s that matches the pattern.

Since p contains exactly one '*', we can split it into two parts:

• A prefix before '*'
• A suffix after '*'

For example:

• "ee*e" becomes prefix "ee" and suffix "e"
• "u*" becomes prefix "u" and suffix ""
• "*abc" becomes prefix "" and suffix "abc"

A substring matches the pattern if:

1. It starts with the prefix.
2. It ends with the suffix.
3. Any characters between them are covered by '*'.

The constraints are very small:

• |s| ≤ 50
• |p| ≤ 50

This means even relatively inefficient solutions would pass. However, there is a very simple and elegant linear solution.

Several edge cases are worth noting:

• The prefix may be empty.
• The suffix may be empty.
• '*' may represent an empty string.
• The prefix and suffix may touch directly with no characters between them.
• The suffix must appear after the matched prefix occurrence.

Because the problem guarantees exactly one '*', we never need to handle multiple wildcards.

Approaches

Brute Force

A straightforward solution is to generate every possible substring of s.

For each substring:

1. Check whether it starts with the prefix.
2. Check whether it ends with the suffix.
3. Verify that the substring is long enough to contain both parts.

If any substring satisfies these conditions, return true.

This works because every possible substring is examined, so any valid match will eventually be found.

However, there are O(n²) substrings, and checking each one may require O(n) work, resulting in O(n³) time in the worst case.

Key Insight

Since there is only one '*', the pattern structure is extremely simple.

Suppose:

p = prefix * suffix

A matching substring must contain:

prefix ... suffix

where the dots represent any sequence of characters, possibly empty.

Therefore, we only need to find:

1. An occurrence of prefix.
2. An occurrence of suffix that starts at or after the end of that prefix occurrence.

If such positions exist, then the substring from the beginning of the prefix to the end of the suffix forms a valid match.

Because the string lengths are tiny, we can simply locate the earliest valid prefix occurrence and then search for the suffix beginning at the end of that prefix.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Enumerate all substrings and validate each
Optimal	O(n)	O(1)	Split pattern into prefix and suffix, then locate them in order

Algorithm Walkthrough

1. Find the position of '*' in the pattern.
2. Split the pattern into:

• prefix = p[:star_index]
• suffix = p[star_index + 1:]

3. Search for the first occurrence of prefix inside s.

If no occurrence exists, return false immediately because every valid match must start with the prefix. 4. Let prefix_end be the index immediately after the matched prefix.

This represents the earliest position where the wildcard portion may begin. 5. Search for suffix inside s, starting from prefix_end.

This guarantees that the suffix appears after the prefix, allowing '*' to cover everything between them. 6. If such a suffix occurrence exists, return true. 7. Otherwise, return false.

Why it works

Let the pattern be:

prefix * suffix

Any valid matching substring must contain an occurrence of prefix followed later by an occurrence of suffix. The wildcard can absorb every character between those two occurrences, including zero characters.

Therefore, the existence of a valid match is equivalent to finding prefix and then finding suffix at or after the end of that prefix occurrence. The algorithm checks exactly this condition, so it is correct.

Problem Understanding

The problem is asking whether a given pattern string p, which contains exactly one asterisk '*', can be matched as a substring of another string s. The asterisk '*' acts as a wildcard that can represent any sequence of characters, including an empty sequence. The input s represents the string we are searching within, and p represents the pattern that may include this single wildcard. The output is a boolean value: true if there exists a substring of s that matches the pattern when the '*' is replaced by some sequence of characters, and false otherwise.

The constraints indicate that both s and p are small, with a maximum length of 50 characters. This means we can afford to perform operations that are quadratic in nature, but linear solutions are still preferable. The key edge cases involve patterns where the '*' is at the start, middle, or end of p, as well as cases where the pattern length exceeds the string length if we replace '*' with an empty string.

Important guarantees include the fact that p contains exactly one '*', so we do not need to handle multiple wildcards. The problem could trip up a naive implementation if we forget to account for the '*' matching zero characters or if we try to match the pattern without considering splitting it into the parts before and after the '*'.

Approaches

The brute-force approach would involve generating all possible substrings of s and attempting to match them with all possible expansions of the '*' in p. For each possible substring of s, we would replace '*' with sequences of characters to see if it matches exactly. This approach is correct but inefficient, because it generates too many possibilities and scales poorly with string length.

The key insight for an optimal solution is to treat the pattern as two fixed parts separated by the '*'. We can split p into a prefix (before '*') and a suffix (after '*'). Then, for any substring of s to match p, it must start with the prefix and end with the suffix. This allows us to slide the prefix along s and check if a corresponding suffix exists after it without generating all possible intermediate substrings.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^3)	O(n)	Generate all substrings of s and attempt all expansions of '*'
Optimal	O(n * m)	O(1)	Split pattern at '*' and match prefix and suffix directly

Algorithm Walkthrough

1. Split the pattern p at the '*' into two strings: prefix (everything before '*') and suffix (everything after '*'). This isolates the parts that must match exactly in s.
2. Iterate over all possible starting indices i in s where the substring could start matching the prefix. The maximum valid i is len(s) - len(prefix) because the prefix must fit.
3. For each starting index i, first check if the substring starting at i matches the prefix.
4. If the prefix matches, calculate the remaining length needed in s after i + len(prefix) to match the suffix. Check if the remaining characters of s are sufficient and if the substring ending at the corresponding index matches the suffix.
5. If both the prefix and suffix conditions are satisfied, return true because a valid substring match exists.
6. If the loop finishes without returning, return false, indicating no substring of s matches the pattern p.

Why it works: The algorithm works because splitting at '*' reduces the problem to checking fixed substrings at the beginning and end of a potential match. Since '*' can represent any sequence, we only need to ensure the characters before and after it match exactly, and the characters in between can vary freely.

Python Solution

class Solution:
    def hasMatch(self, s: str, p: str) -> bool:
        star_index = p.index("*")

        prefix = p[:star_index]
        suffix = p[star_index + 1:]

        prefix_pos = s.find(prefix)

        if prefix_pos == -1:
            return False

        prefix_end = prefix_pos + len(prefix)

        suffix_pos = s.find(suffix, prefix_end)

        return suffix_pos != -1

The implementation begins by locating the wildcard and splitting the pattern into its fixed prefix and suffix portions.

The method find() is then used to locate the prefix within s. If the prefix does not exist, no valid match is possible.

Once the prefix is found, the algorithm computes the first position immediately after that prefix. Any characters between this position and the suffix can be matched by the wildcard.

Finally, another find() searches for the suffix beginning from that position. If such an occurrence exists, the pattern can be transformed into a substring of s, so the method returns True. star_index = p.index('*') prefix = p[:star_index] suffix = p[star_index+1:] n, m1, m2 = len(s), len(prefix), len(suffix)

    for i in range(n - m1 + 1):
        if s[i:i+m1] == prefix:
            remaining_length = n - (i + m1)
            if remaining_length >= m2 and s[i+m1:i+m1+m2] == suffix:
                return True
    return False

The implementation first finds the index of the `'*'` and splits the pattern into `prefix` and `suffix`. It then iterates over all possible starting positions in `s` where the prefix could fit. For each candidate start, it checks if the prefix matches exactly. If the prefix matches, it checks if the remaining substring can accommodate the suffix and if the suffix matches. The algorithm returns `true` if both match, otherwise it returns `false`.

## Go Solution

```go
func hasMatch(s string, p string) bool {
	starIndex := -1

	for i, ch := range p {
		if ch == '*' {
			starIndex = i
			break
		}
	}

	prefix := p[:starIndex]
	suffix := p[starIndex+1:]

	prefixPos := -1
	for i := 0; i+len(prefix) <= len(s); i++ {
		if s[i:i+len(prefix)] == prefix {
			prefixPos = i
			break
		}
	}

	if prefixPos == -1 {
		return false
	}

	prefixEnd := prefixPos + len(prefix)

	for i := prefixEnd; i+len(suffix) <= len(s); i++ {
		if s[i:i+len(suffix)] == suffix {
			return true
		}
	}

	return false
}

The Go solution follows the same logic as the Python version. Since Go does not provide a direct equivalent of Python's find() method on strings, the code performs simple substring scans manually.

There are no concerns about integer overflow because all lengths are at most 50. Empty prefixes and empty suffixes are handled naturally because slicing and comparisons with empty strings work correctly.

Worked Examples

Example 1

s = "leetcode"
p = "ee*e"

Split the pattern:

Variable	Value
prefix	"ee"
suffix	"e"

Find prefix:

Operation	Result
s.find("ee")	1

Compute:

Variable	Value
prefix_end	3

Search for suffix from index 3:

Operation	Result
s.find("e", 3)	7

Since a suffix occurrence exists, return:

true

Matching substring:

eetcode

Example 2

s = "car"
p = "c*v"

Split:

Variable	Value
prefix	"c"
suffix	"v"

Find prefix:

Operation	Result
s.find("c")	0

Compute:

Variable	Value
prefix_end	1

Search for suffix:

Operation	Result
s.find("v", 1)	-1

No suffix exists after the prefix.

false

Example 3

s = "luck"
p = "u*"

Split:

Variable	Value
prefix	"u"
suffix	""

Find prefix:

Operation	Result
s.find("u")	1

Compute:

Variable	Value
prefix_end	2

Search for empty suffix:

Operation	Result
s.find("", 2)	2

An empty suffix always matches.

true

starIndex := -1
for i, ch := range p {
    if ch == '*' {
        starIndex = i
        break
    }
}
prefix := p[:starIndex]
suffix := p[starIndex+1:]
n, m1, m2 := len(s), len(prefix), len(suffix)

for i := 0; i <= n-m1; i++ {
    if s[i:i+m1] == prefix {
        remainingLength := n - (i + m1)
        if remainingLength >= m2 && s[i+m1:i+m1+m2] == suffix {
            return true
        }
    }
}
return false

}

In Go, the algorithm is nearly identical. We iterate to find the `'*'` index manually and slice the strings accordingly. Go requires explicit bounds checking and slicing syntax, but the logic mirrors the Python solution.

## Worked Examples

**Example 1: s = "leetcode", p = "ee*e"**

| Step | i | prefix match? | remaining_length | suffix match? | Result |
| --- | --- | --- | --- | --- | --- |
| 1 | 0 | "le" != "ee" | - | - | continue |
| 2 | 1 | "ee" == "ee" | 6 - (1+2)=3 | "cod" != "e" | continue |
| 3 | 2 | "et" != "ee" | - | - | continue |
| 4 | 3 | "tc" != "ee" | - | - | continue |
| 5 | 4 | "co" != "ee" | - | - | continue |
| 6 | 5 | "od" != "ee" | - | - | continue |
| 7 | 6 | "de" != "ee" | - | - | continue |
| 8 | 1 (prefix match at i=1) | suffix "e" matches at i+len(prefix)+len(*) | true |  |  |

**Example 2: s = "car", p = "c*v"**

No index satisfies both prefix "c" and suffix "v", returns false.

__Example 3: s = "luck", p = "u_"_*

Prefix "u" matches at index 1, suffix is empty, returns true.

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n) | Each search scans the string at most once |
| Space | O(1) | Only a few variables are stored |

Although string-search implementations may internally use different algorithms, with the given constraints the overall work is linear in the length of `s`. No auxiliary data structures proportional to the input size are required.
| Time | O(n * m) | We iterate through each position in `s` for prefix matching, and suffix check is O(m) where m is length of suffix |
| Space | O(1) | Only a few integer and substring variables are used, no additional data structures |

The complexity is reasonable given n, m <= 50.

## Test Cases

sol = Solution()

assert sol.hasMatch("leetcode", "eee") is True # example 1 assert sol.hasMatch("car", "cv") is False # example 2 assert sol.hasMatch("luck", "u*") is True # example 3

assert sol.hasMatch("abc", "*") is True # wildcard matches empty substring assert sol.hasMatch("abc", "c") is True # empty prefix assert sol.hasMatch("abc", "a") is True # empty suffix

assert sol.hasMatch("abc", "abc") is True # wildcard matches empty string assert sol.hasMatch("abc", "ac") is True # wildcard matches middle character

assert sol.hasMatch("abc", "d*") is False # prefix missing assert sol.hasMatch("abc", "*d") is False # suffix missing

assert sol.hasMatch("aaaa", "aaa") is True # repeated characters assert sol.hasMatch("abcd", "bcd") is True # match inside string

assert sol.hasMatch("abcd", "cda") is False # suffix cannot appear after prefix assert sol.hasMatch("a", "a") is True # minimum length source string assert sol.hasMatch("a", "*a") is True # minimum length source string

assert sol.hasMatch("abcde", "abde") is True # long exact span assert sol.hasMatch("abcde", "abf") is False # suffix absent

### Test Summary

| Test | Why |
| --- | --- |
| `"leetcode", "ee*e"` | Official example |
| `"car", "c*v"` | Official negative example |
| `"luck", "u*"` | Official example with empty suffix |
| `"abc", "*"` | Wildcard only |
| `"abc", "*c"` | Empty prefix |
| `"abc", "a*"` | Empty suffix |
| `"abc", "ab*c"` | Wildcard matches empty string |
| `"abc", "a*c"` | Wildcard matches non-empty string |
| `"abc", "d*"` | Missing prefix |
| `"abc", "*d"` | Missing suffix |
| `"aaaa", "aa*a"` | Repeated characters |
| `"abcd", "bc*d"` | Internal substring match |
| `"abcd", "cd*a"` | Incorrect ordering |
| `"a", "a*"` | Smallest source string |
| `"a", "*a"` | Smallest source string with empty prefix |
| `"abcde", "ab*de"` | Full span match |
| `"abcde", "ab*f"` | Suffix absent |

## Edge Cases

### Empty Prefix

Patterns such as `"*abc"` have no fixed prefix. A common bug is assuming a prefix always exists and attempting to search for it.

In the implementation, `prefix` becomes an empty string. Python's `find("")` returns `0`, which correctly indicates that matching may begin at the start of the string. The algorithm therefore works without any special handling.

### Empty Suffix

Patterns such as `"abc*"` have no fixed suffix. Any substring beginning with `"abc"` should be considered valid.

The implementation searches for an empty string after the prefix. Since an empty string is always found at the search position, the algorithm correctly returns `True` whenever the prefix exists.

### Wildcard Matching an Empty Sequence

The problem explicitly allows `'*'` to represent zero characters. Patterns like `"ab*c"` should therefore match `"abc"`.

The algorithm searches for the suffix beginning exactly at `prefix_end`. If the suffix starts immediately after the prefix, the gap length is zero, which naturally represents the wildcard matching an empty sequence.

### Repeated Character Ambiguity

Strings such as `"aaaa"` and patterns such as `"aa*a"` can have many possible prefix and suffix occurrences. A careless implementation might pair the wrong occurrences.

The algorithm only needs to find one valid ordering where the suffix appears at or after the end of a prefix occurrence. As soon as such an arrangement exists, a matching substring exists, so the method correctly returns `True`.
# provided examples
assert Solution().hasMatch("leetcode", "ee*e") == True  # Example 1
assert Solution().hasMatch("car", "c*v") == False      # Example 2
assert Solution().hasMatch("luck", "u*") == True       # Example 3

# boundary tests
assert Solution().hasMatch("a", "*") == True           # single char s, pattern is only '*'
assert Solution().hasMatch("abc", "a*c") == True      # '*' in middle
assert Solution().hasMatch("abc", "abc*") == True     # '*' at end
assert Solution().hasMatch("abc", "*abc") == True     # '*' at start
assert Solution().hasMatch("abc", "d*") == False      # no match
assert Solution().hasMatch("aaa", "a*a") == True      # repeating chars

Test	Why
"leetcode", "ee*e"	Checks normal prefix and suffix match
"car", "c*v"	Ensures false is returned when no match
"luck", "u*"	Checks matching with empty suffix
"a", "*"	Single character and only wildcard
"abc", "a*c"	Wildcard in middle
"abc", "abc*"	Wildcard at end
"abc", "*abc"	Wildcard at start
"d*", "abc"	Non-matching prefix
"aaa", "a*a"	Repeating characters

Edge Cases

The first edge case is when