Easy

题目描述

给你一个字符串 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 仅包含小写英文字母和恰好一个 '*'

提示：

  • 将模式分成两个字符串，在原字符串中搜索。

解题思路

这道题的核心思路是将包含通配符 * 的模式字符串分割成两部分：* 前面的前缀和 * 后面的后缀。

解法分析：

  1. 字符串分割法（推荐）：找到 * 的位置，将模式字符串分成前缀和后缀两部分。然后在原字符串 s 中寻找所有可能的匹配位置。

  2. 暴力匹配法：枚举 s 的所有子串，检查是否能通过某种 * 的替换方式匹配模式。

具体实现思路：

对于分割法，我们需要：

  • 找到模式字符串中 * 的位置
  • 获取前缀（* 之前的部分）和后缀（* 之后的部分）
  • 在字符串 s 中寻找前缀的所有出现位置
  • 对于每个前缀位置，检查从该位置开始是否能找到对应的后缀
  • 关键点：前缀结束位置到后缀开始位置之间可以有任意字符（包括空字符串）

这种方法的优势是逻辑清晰，易于理解和实现。时间复杂度在最坏情况下为 O(n²)，其中 n 是字符串长度。

代码实现

class Solution {
public:
    bool hasMatch(string s, string p) {
        int star_pos = p.find('*');
        string prefix = p.substr(0, star_pos);
        string suffix = p.substr(star_pos + 1);
        
        int n = s.length();
        int prefix_len = prefix.length();
        int suffix_len = suffix.length();
        
        // 枚举前缀在s中的所有可能位置
        for (int i = 0; i <= n - prefix_len; i++) {
            // 检查前缀是否匹配
            if (s.substr(i, prefix_len) == prefix) {
                // 枚举后缀在s中的所有可能位置
                for (int j = i + prefix_len; j <= n - suffix_len; j++) {
                    // 检查后缀是否匹配
                    if (s.substr(j, suffix_len) == suffix) {
                        return true;
                    }
                }
            }
        }
        
        return false;
    }
};

class Solution:
    def hasMatch(self, s: str, p: str) -> bool:
        star_pos = p.index('*')
        prefix = p[:star_pos]
        suffix = p[star_pos + 1:]
        
        n = len(s)
        prefix_len = len(prefix)
        suffix_len = len(suffix)
        
        # 枚举前缀在s中的所有可能位置
        for i in range(n - prefix_len + 1):
            # 检查前缀是否匹配
            if s[i:i + prefix_len] == prefix:
                # 枚举后缀在s中的所有可能位置
                for j in range(i + prefix_len, n - suffix_len + 1):
                    # 检查后缀是否匹配
                    if s[j:j + suffix_len] == suffix:
                        return True
        
        return False

public class Solution {
    public bool HasMatch(string s, string p) {
        int starPos = p.IndexOf('*');
        string prefix = p.Substring(0, starPos);
        string suffix = p.Substring(starPos + 1);
        
        int n = s.Length;
        int prefixLen = prefix.Length;
        int suffixLen = suffix.Length;
        
        // 枚举前缀在s中的所有可能位置
        for (int i = 0; i <= n - prefixLen; i++) {
            // 检查前缀是否匹配
            if (s.Substring(i, prefixLen) == prefix) {
                // 枚举后缀在s中的所有可能位置
                for (int j = i + prefixLen; j <= n - suffixLen; j++) {
                    // 检查后缀是否匹配
                    if (s.Substring(j, suffixLen) == suffix) {
                        return true;
                    }
                }
            }
        }
        
        return false;
    }
}

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var hasMatch = function(s, p) {
    const starIndex = p.indexOf('*');
    const prefix = p.substring(0, starIndex);
    const suffix = p.substring(starIndex + 1);
    
    for (let i = 0; i <= s.length - prefix.length - suffix.length; i++) {
        if (s.substring(i, i + prefix.length) === prefix) {
            for (let j = i + prefix.length; j <= s.length - suffix.length; j++) {
                if (s.substring(j, j + suffix.length) === suffix) {
                    return true;
                }
            }
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)其中 n 是字符串 s 的长度。外层循环枚举前缀位置，内层循环枚举后缀位置
空间复杂度O(1)只使用了常数额外空间存储前缀、后缀和几个变量

相关题目