# Substring Matching Pattern
**Difficulty:** EASY
[External](https://leetcode.com/problems/substring-matching-pattern)
Canonical: https://scaleengineer.com/dsa/problems/substring-matching-pattern
**Patterns:** [String Matching](https://scaleengineer.com/dsa/patterns/string-matching)
**Data structures:** String
---
## Problem
You are given a string `s` and a pattern string `p`, where `p` contains **exactly one** `'*'` character.

The `'*'` in `p` can be replaced with any sequence of zero or more characters.

Return `true` if `p` can be made a substring of `s`, and `false` otherwise.

**Example 1:**

**Input:** s = "leetcode", p = "ee\*e"

**Output:** true

**Explanation:**

By replacing the `'*'` with `"tcod"`, the substring `"eetcode"` matches the pattern.

**Example 2:**

**Input:** s = "car", p = "c\*v"

**Output:** false

**Explanation:**

There is no substring matching the pattern.

**Example 3:**

**Input:** s = "luck", p = "u\*"

**Output:** true

**Explanation:**

The substrings `"u"`, `"uc"`, and `"uck"` match the pattern.

**Constraints:**

* `1 <= s.length <= 50`
* `1 <= p.length <= 50 `
* `s` contains only lowercase English letters.
* `p` contains only lowercase English letters and exactly one `'*'`

# Approaches
## Brute-force Substring Check
This approach involves generating every possible substring of `s` and checking if it matches the pattern `p`. A substring matches the pattern if it starts with the pattern's prefix, ends with its suffix, and has a sufficient length.
**Time:** O(N^3 * M), where N is the length of `s` and M is the length of `p`. The two nested loops give O(N^2) iterations. Inside the loop, creating a substring can take O(N) time, and `startsWith`/`endsWith` can take O(M) time. This results in a very high time complexity. · **Space:** O(N), where N is the length of `s`. This is for storing the generated substring `sub` in each iteration.
**Pros:** Simple to conceptualize and implement.; Directly translates the problem definition into code.
**Cons:** Highly inefficient due to the generation and checking of all O(N^2) substrings.; Likely to result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
The fundamental idea is to test every single substring of `s` against the pattern `p`. We begin by splitting the pattern `p` at the `*` character to get a `prefix` and a `suffix`. Then, we use two nested loops to generate all substrings of `s`. The outer loop selects the starting index `i`, and the inner loop selects the ending index `j`. For each substring `s.substring(i, j)`, we verify if it could match the pattern. A match is valid if the substring's length is at least the combined length of the prefix and suffix, the substring begins with the `prefix`, and it ends with the `suffix`. If we find such a substring, we can immediately conclude that the pattern matches and return `true`. If the loops complete without finding any such substring, it means no match is possible, and we return `false`.

```java
class Solution {
    public boolean matchPattern(String s, String p) {
        int starIndex = p.indexOf('*');
        String prefix = p.substring(0, starIndex);
        String suffix = p.substring(starIndex + 1);

        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j <= s.length(); j++) {
                String sub = s.substring(i, j);
                if (sub.length() >= prefix.length() + suffix.length()) {
                    if (sub.startsWith(prefix) && sub.endsWith(suffix)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}
```
### Algorithm
- First, parse the pattern `p` to extract the prefix and suffix parts by finding the `*` character. Let's call them `prefix` and `suffix`.
- Then, iterate through all possible start and end indices of substrings in `s`. For each substring `sub`:
    - Check if `sub`'s length is at least `prefix.length() + suffix.length()`.
    - Check if `sub` starts with `prefix`.
    - Check if `sub` ends with `suffix`.
- If all three conditions are met for any substring, a match is found, and we return `true`.
- If all substrings are checked and no match is found, we return `false`.

## Iterative Search for Prefix and Suffix
This approach improves upon the brute-force method by avoiding the generation of all substrings. Instead, it searches for occurrences of the `prefix` in `s`. For each found `prefix`, it then searches for the `suffix` in the remainder of the string.
**Time:** O(N*M) in practice. The outer `while` loop can run up to N times. The `indexOf` method takes O((N-k)*M) where k is the starting index. In total, this can be considered roughly O(N*M) with optimized `indexOf` implementations. In the worst-case with a naive `indexOf`, it could be O(N^2 * M). · **Space:** O(M), where M is the length of `p`, for storing the `prefix` and `suffix` strings.
**Pros:** More efficient than the brute-force approach as it avoids generating and checking every substring.; It's a more targeted search.
**Cons:** Can be inefficient if the `prefix` occurs very frequently in `s`, leading to many repeated searches for the `suffix`.
### Explanation
Instead of checking every substring, we can be more direct. We first parse `p` to get the `prefix` and `suffix`. The goal is to find an occurrence of `prefix` followed by an occurrence of `suffix` somewhere later in the string `s`. We can achieve this by iterating through all possible start positions of the `prefix`. We use `s.indexOf(prefix, fromIndex)` in a loop to find each occurrence of the `prefix`. For each `prefix` found at `prefixIndex`, we then search for the `suffix` but only in the part of the string that comes after the `prefix` ends, i.e., starting from index `prefixIndex + prefix.length()`. If `s.indexOf(suffix, ...)` finds a match, we have satisfied the pattern and can return `true`. If the `suffix` is not found, we continue to the next occurrence of the `prefix` by updating our search start position. If we exhaust all occurrences of `prefix` without finding a subsequent `suffix`, we return `false`.

```java
class Solution {
    public boolean matchPattern(String s, String p) {
        int starIndex = p.indexOf('*');
        String prefix = p.substring(0, starIndex);
        String suffix = p.substring(starIndex + 1);

        int fromIndex = 0;
        while (true) {
            int prefixIndex = s.indexOf(prefix, fromIndex);
            if (prefixIndex == -1) {
                break; // No more occurrences of prefix
            }

            int suffixSearchStart = prefixIndex + prefix.length();
            int suffixIndex = s.indexOf(suffix, suffixSearchStart);
            if (suffixIndex != -1) {
                return true; // Found a valid match
            }
            
            fromIndex = prefixIndex + 1;
        }

        return false;
    }
}
```
### Algorithm
- Find the index of `*` in `p`.
- Extract `prefix` and `suffix`.
- Initialize `searchFromIndex = 0`.
- Loop:
    - Find the index of `prefix` in `s` starting from `searchFromIndex`. Let it be `prefixIndex`.
    - If `prefix` is not found (`prefixIndex == -1`), break the loop.
    - Calculate the starting position for the suffix search: `suffixSearchStart = prefixIndex + prefix.length()`.
    - Find the index of `suffix` in `s` starting from `suffixSearchStart`. Let it be `suffixIndex`.
    - If `suffix` is found (`suffixIndex != -1`), return `true`.
    - Update `searchFromIndex = prefixIndex + 1` to find the next occurrence of `prefix`.
- If the loop completes, return `false`.

## Optimized Search with First and Last Occurrences
This is the most efficient approach. It leverages a key insight: if a match exists, there must be an occurrence of the `prefix` that appears before an occurrence of the `suffix`. To check this, we only need to find the first occurrence of the `prefix` and the last occurrence of the `suffix`.
**Time:** O(N * M), where N is the length of `s` and M is the length of `p`. This complexity is dominated by the `indexOf` and `lastIndexOf` calls. With standard library optimizations (like KMP or Boyer-Moore), the complexity is closer to O(N + M). · **Space:** O(M), where M is the length of `p`, for storing the `prefix` and `suffix` strings.
**Pros:** Extremely efficient as it only requires two passes (or one for each search) over the string.; Simple and concise implementation.
**Cons:** The logic might be slightly less intuitive to come up with compared to a direct iterative search.
### Explanation
This optimized approach is based on a simple logical deduction. For a pattern `prefix*suffix` to match, there must be some instance of `prefix` at index `i` and some instance of `suffix` at index `j` in `s` such that `i + prefix.length() <= j`. To check if such a pair `(i, j)` exists, we can check the most favorable case: the earliest possible `prefix` and the latest possible `suffix`. 

We find the index of the very first occurrence of `prefix` using `s.indexOf(prefix)`. Let this be `firstPrefixIndex`. Then, we find the index of the very last occurrence of `suffix` using `s.lastIndexOf(suffix)`. Let this be `lastSuffixIndex`. 

If either `prefix` or `suffix` doesn't exist in `s`, a match is impossible. If both exist, we just need to check if the first `prefix` ends at or before the last `suffix` begins. This is true if `firstPrefixIndex + prefix.length() <= lastSuffixIndex`. If this condition holds, we have found a valid configuration, and we return `true`. If it doesn't, it means every occurrence of `prefix` is too late to be followed by any occurrence of `suffix`, so no match is possible, and we return `false`.

```java
class Solution {
    public boolean matchPattern(String s, String p) {
        int starIndex = p.indexOf('*');
        String prefix = p.substring(0, starIndex);
        String suffix = p.substring(starIndex + 1);

        int firstPrefixIndex = s.indexOf(prefix);
        if (firstPrefixIndex == -1) {
            return false;
        }

        int lastSuffixIndex = s.lastIndexOf(suffix);
        if (lastSuffixIndex == -1) {
            return false;
        }

        return firstPrefixIndex + prefix.length() <= lastSuffixIndex;
    }
}
```
### Algorithm
- Find the index of `*` in `p`.
- Extract `prefix` and `suffix`.
- Find the index of the first occurrence of `prefix` in `s`. If not found, return `false`.
- Find the index of the last occurrence of `suffix` in `s`. If not found, return `false`.
- Check if the end of the first `prefix` (`firstPrefixIndex + prefix.length()`) is before or at the start of the last `suffix` (`lastSuffixIndex`).
- If `firstPrefixIndex + prefix.length() <= lastSuffixIndex`, return `true`.
- Otherwise, return `false`.

# Solutions
### Java

```java
class Solution {
public
  boolean hasMatch(String s, String p) {
    int i = 0;
    for (String t : p.split("\\*")) {
      int j = s.indexOf(t, i);
      if (j == -1) {
        return false;
      }
      i = j + t.length();
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool hasMatch(string s, string p) {
    int i = 0;
    int pos = 0;
    int start = 0, end;
    while ((end = p.find("*", start)) != string ::npos) {
      string t = p.substr(start, end - start);
      pos = s.find(t, i);
      if (pos == string ::npos) {
        return false;
      }
      i = pos + t.length();
      start = end + 1;
    }
    string t = p.substr(start);
    pos = s.find(t, i);
    if (pos == string ::npos) {
      return false;
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def hasMatch(self, s: str, p: str) -> bool: i = 0 for t in p . split("*"): j = s . find(t, i) if j == - 1: return False i = j + len(t) return True

```