Substring Matching Pattern

Substring Matching Pattern

What is this problem about?

The "Substring Matching Pattern" is an easy-rated string problem that asks you to check if a string s matches a pattern p. The pattern p consists of letters and exactly one asterisk (*). The asterisk can represent any sequence of characters (including an empty sequence). To match, the part of the pattern before the asterisk must appear in s, and the part after the asterisk must appear later in s without overlapping with the first part.

Why is this asked in interviews?

Amazon and other companies use this as a simple check for string manipulation skills. It tests whether a candidate can correctly split a string based on a delimiter and find the positions of substrings. While it's relatively simple, it requires attention to detail regarding the "non-overlapping" constraint and handling cases where the asterisk is at the very beginning or end of the pattern.

Algorithmic pattern used

This is a String Search problem.

1. Split the pattern p at the asterisk into prefix and suffix.
2. Find the first occurrence of the prefix in s.
3. If the prefix is found at index i, search for the suffix in the part of s starting from index i + len(prefix).
4. If both are found in the correct order, return true. This can be implemented using standard library functions like find() or indexOf().

Example explanation (use your own example)

s = "leetcode", p = "ee*de"

1. Split pattern: prefix = "ee", suffix = "de".
2. Find "ee" in "leetcode". Found at index 1.
3. Search for "de" starting from index 1 + 2 = 3.
4. "de" is found at the very end (index 6).
5. Result: True. If p was "ee*tc", it would fail because "tc" does not appear after "ee".

Common mistakes candidates make

One common mistake is allowing the prefix and suffix to overlap. For example, if s = "ab" and p = "ab*b", the "b" in the prefix and the "b" in the suffix should be different characters. Another mistake is not correctly handling the case where the asterisk is at the start or end, which would result in an empty prefix or suffix. In most languages, searching for an empty string always returns the current index, so the logic usually holds if implemented carefully.

Interview preparation tip

For the Substring Matching Pattern coding problem, keep your solution as simple as possible. Use the built-in string searching methods of your language. Mention that the time complexity is O(N + M) where N and M are the lengths of the string and pattern respectively. It's a great example of "Surgical String Slicing."