3407. 子字符串匹配模式

English Version

题目描述

给你一个字符串 s 和一个模式字符串 p ，其中 p 恰好 包含 一个 '*' 符号。

p 中的 '*' 符号可以被替换为零个或多个字符组成的任意字符序列。

如果 p 可以变成 s 的 子字符串，那么返回 true ，否则返回 false 。

 

示例 1：

输入：s = "leetcode", p = "ee*e"

输出：true

解释：

将 '*' 替换为 "tcod" ，子字符串 "eetcode" 匹配模式串。

示例 2：

输入：s = "car", p = "c*v"

输出：false

解释：

不存在匹配模式串的子字符串。

示例 3：

输入：s = "luck", p = "u*"

输出：true

解释：

子字符串 "u" ，"uc" 和 "uck" 都匹配模式串。

 

提示：

• 1 <= s.length <= 50
• 1 <= p.length <= 50
• s 只包含小写英文字母。
• p 只包含小写英文字母和一个 '*' 符号。

解法

方法一

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