What does '*' represent in the Substring Matching Pattern problem?

'*' can be replaced by any sequence of characters, including an empty string, in the pattern.

How do I efficiently check substrings against the pattern?

Split the pattern into prefix and suffix and check each substring of sufficient length for alignment with both parts.

Can the pattern match an empty substring?

Only if the prefix and suffix are both empty or if '*' accounts for the entire substring.

What is the time complexity for this approach?

Roughly O(n * m), where n is the length of s and m is the length of p, because each substring may require prefix and suffix checks.

Are there edge cases I should be careful about?

Yes, especially when '*' matches zero characters or when prefix/suffix length is close to s length, requiring careful substring bounds checking.

#3407

Easy

auto_awesomestring·结合·string·matching

LeetCode 题解工作台

子字符串匹配模式

给你一个字符串 s 和一个模式字符串 p ，其中 p 恰好包含一个 '*' 符号。 p 中的 '*' 符号可以被替换为零个或多个字符组成的任意字符序列。如果 p 可以变成 s 的子字符串，那么返回 true ，否则返回 false 。示例 1：输入： s = "leetcode", p…

字符串字符串匹配

题目描述

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

lightbulb

解题思路

方法一：字符串匹配

根据题目描述，* 可以被替换为零个或多个字符组成的任意字符序列，因此我们可以将模式字符串 $p$ 按照 * 分割成若干个子串，如果这些子串依次出现在字符串 $s$ 中且顺序不变，则说明 $p$ 可以变成 $s$ 的子字符串。

因此，我们首先初始化一个指针 $i$ 指向字符串 $s$ 的起始位置，然后遍历模式字符串 $p$ 按照 * 分割得到的每个子串 $t$ ，在字符串 $s$ 中从位置 $i$ 开始查找子串 $t$ ，如果找到了，则将指针 $i$ 移动到子串 $t$ 的末尾位置继续查找下一个子串；如果找不到，则说明模式字符串 $p$ 不能变成字符串 $s$ 的子字符串，返回 $\text{false}$ 。如果所有子串都找到了，则返回 $\text{true}$ 。

时间复杂度 $O(n \times m)$ ，空间复杂度 $O(m)$ 。其中 $n$ 和 $m$ 分别是字符串 $s$ 和模式字符串 $p$ 的长度。

1

2

3

4

5

6

7

8

9

10

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

speed

复杂度分析

指标	值
时间	complexity depends on scanning s and checking prefix and suffix matches, roughly O(n * m) where n = s.length and m = p.length. Space complexity is O(1) extra if no substring storage is needed.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Notice the pattern contains exactly one '*' indicating a split-match approach.
question_mark
Ask about handling empty matches for the '*' character.
question_mark
Check if your substring scanning handles all offsets efficiently.

warning

常见陷阱

外企场景

error
Forgetting that '*' can match zero characters, leading to missed valid matches.
error
Checking substrings shorter than prefix+suffix, which cannot match.
error
Incorrectly matching prefix and suffix positions causing false negatives.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Patterns containing multiple '*' characters requiring backtracking or DP.
arrow_right_alt
Case-insensitive matching or Unicode string support.
arrow_right_alt
Finding all matching substrings instead of just returning true/false.

help

常见问题

外企场景

继续练习

#3455 最短匹配子字符串 #3474 字典序最小的生成字符串 #3303 第一个几乎相等子字符串的下标