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:

Example 2:

Example 3:

 

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.

Python3

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

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

C++

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

Go

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
}

TypeScript

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

Rust

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