3407. Substring Matching Pattern

Description

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

Solutions

Solution 1: String Matching

According to the problem description, * can be replaced by any sequence of zero or more characters, so we can split the pattern string \(p\) by * into several substrings. If these substrings appear in order in the string \(s\), then \(p\) can become a substring of \(s\).

Therefore, we first initialize a pointer \(i\) to the start of string \(s\), then iterate over each substring \(t\) obtained by splitting the pattern string \(p\) by *. For each \(t\), we search for it in \(s\) starting from position \(i\). If it is found, we move the pointer \(i\) to the end of \(t\) and continue searching for the next substring. If it is not found, it means the pattern string \(p\) cannot become a substring of \(s\), and we return \(\text{false}\). If all substrings are found, we return \(\text{true}\).

The time complexity is \(O(n \times m)\), and the space complexity is \(O(m)\), where \(n\) and \(m\) are the lengths of strings \(s\) and \(p\), respectively.

Python3JavaC++GoTypeScriptRust

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

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;
    }
}

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;
    }
};

func hasMatch(s string, p string) bool {
    i := 0
    for _, t := range strings.Split(p, "*") {
        j := strings.Index(s[i:], t)
        if j == -1 {
            return false
        }
        i += j + len(t)
    }
    return true
}

function hasMatch(s: string, p: string): boolean {
    let i = 0;
    for (const t of p.split('*')) {
        const j = s.indexOf(t, i);
        if (j === -1) {
            return false;
        }
        i = j + t.length;
    }
    return true;
}

impl Solution {
    pub fn has_match(s: String, p: String) -> bool {
        let mut i = 0usize;
        for t in p.split('*') {
            if let Some(j) = s[i..].find(t) {
                i += j + t.len();
            } else {
                return false;
            }
        }
        true
    }
}

3407. Substring Matching Pattern

Description

Solutions

Solution 1: String Matching

Comments