Substring Matching Pattern

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

1
2
3
4
5


Input: s = "leetcode", p = "ee*e"
Output: true
Explanation:
By replacing the `'*'` with `"tcod"`, the substring `"eetcode"` matches the
pattern.

Example 2

1
2
3
4


Input: s = "car", p = "c*v"
Output: false
Explanation:
There is no substring matching the pattern.

Example 3

1
2
3
4


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 '*'

Examples

Solution

Method 1 - Greedy Prefix/Suffix Match

Intuition

The pattern p contains exactly one *, which can match any sequence (including empty) of characters. We can split p into a prefix (before *) and a suffix (after *). For p to match a substring of s, there must exist a substring in s that starts with the prefix and ends with the suffix, with any (possibly empty) string in between.

Approach

Split p into prefix and suffix at the *.
For every possible substring of s of length at least len(prefix) + len(suffix), check if it starts with prefix and ends with suffix.
If any such substring exists, return true. Otherwise, return false.

This is efficient because both s and p are small (≤ 50).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution {
public:
    bool matchSubstring(string s, string p) {
        int star = p.find('*');
        string pre = p.substr(0, star);
        string suf = p.substr(star + 1);
        int n = s.size(), m = pre.size(), k = suf.size();
        for (int i = 0; i + m + k <= n; ++i) {
            if (s.substr(i, m) == pre && s.substr(i + m + (n - i - m - k), k) == suf) {
                // Actually, we need to check all substrings of length >= m + k
                for (int len = m + k; i + len <= n; ++len) {
                    if (s.substr(i, m) == pre && s.substr(i + len - k, k) == suf)
                        return true;
                }
            }
        }
        return false;
    }
};
// Leetcode signature:
// bool matchSubstring(string s, string p);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


func matchSubstring(s string, p string) bool {
    star := -1
    for i, c := range p {
        if c == '*' {
            star = i
            break
        }
    }
    pre := p[:star]
    suf := p[star+1:]
    n, m, k := len(s), len(pre), len(suf)
    for i := 0; i <= n-m-k; i++ {
        for l := m + k; i+l <= n; l++ {
            if s[i:i+m] == pre && s[i+l-k:i+l] == suf {
                return true
            }
        }
    }
    return false
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
    public boolean matchSubstring(String s, String p) {
        int star = p.indexOf('*');
        String pre = p.substring(0, star);
        String suf = p.substring(star + 1);
        int n = s.length(), m = pre.length(), k = suf.length();
        for (int i = 0; i <= n - m - k; i++) {
            for (int len = m + k; i + len <= n; len++) {
                if (s.substring(i, i + m).equals(pre) && s.substring(i + len - k, i + len).equals(suf)) {
                    return true;
                }
            }
        }
        return false;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


fun matchSubstring(s: String, p: String): Boolean {
    val star = p.indexOf('*')
    val pre = p.substring(0, star)
    val suf = p.substring(star + 1)
    val n = s.length; val m = pre.length; val k = suf.length
    for (i in 0..n - m - k) {
        for (len in m + k..n - i) {
            if (s.substring(i, i + m) == pre && s.substring(i + len - k, i + len) == suf) {
                return true
            }
        }
    }
    return false
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


def matchSubstring(s: str, p: str) -> bool:
    star = p.index('*')
    pre = p[:star]
    suf = p[star+1:]
    n, m, k = len(s), len(pre), len(suf)
    for i in range(n - m - k + 1):
        for l in range(m + k, n - i + 1):
            if s[i:i+m] == pre and s[i+l-k:i+l] == suf:
                return True
    return False

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


pub fn match_substring(s: String, p: String) -> bool {
    let star = p.find('*').unwrap();
    let pre = &p[..star];
    let suf = &p[star+1..];
    let n = s.len();
    let m = pre.len();
    let k = suf.len();
    for i in 0..=n - m - k {
        for l in m + k..=n - i {
            if &s[i..i+m] == pre && &s[i+l-k..i+l] == suf {
                return true;
            }
        }
    }
    false
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


function matchSubstring(s: string, p: string): boolean {
    const star = p.indexOf('*');
    const pre = p.slice(0, star);
    const suf = p.slice(star + 1);
    const n = s.length, m = pre.length, k = suf.length;
    for (let i = 0; i <= n - m - k; i++) {
        for (let l = m + k; i + l <= n; l++) {
            if (s.slice(i, i + m) === pre && s.slice(i + l - k, i + l) === suf) {
                return true;
            }
        }
    }
    return false;
}

Complexity

⏰ Time complexity: O(n^2) (since for each possible start, we check all possible substring lengths)
🧺 Space complexity: O(1)

Problem#

Example 1#

Example 2#

Example 3#

Constraints#

Examples#

Solution#

Method 1 - Greedy Prefix/Suffix Match#

Intuition#

Approach#

Code#

Complexity#