力扣3407题解：带通配符的字符串匹配算法

一、问题分析

这道题目要求我们判断一个包含单个星号通配符的模式字符串p是否可以匹配目标字符串s的任意子字符串。星号可以匹配零个或多个任意字符，这增加了问题的复杂性。

关键点：

1. 模式字符串p中恰好包含一个'*'

2. '*'可以匹配任意长度的字符序列（包括空序列）

3. 需要判断p是否能匹配s的任意连续子串

二、解题思路

我们可以将问题分解为以下几个步骤：

1. 找到模式字符串p中的星号位置

2. 将p分为星号前的前缀和星号后的后缀

3. 在s中寻找能够匹配前缀和后缀的子串

4. 前缀和后缀之间的部分由星号匹配

三、C++代码实现

class Solution {
public:
    bool hasMatch(string s, string p) {
        // 找到星号的位置
        size_t star_pos = p.find('*');
        string prefix = p.substr(0, star_pos); // 星号前部分
        string suffix = p.substr(star_pos + 1); // 星号后部分
        
        // 特殊情况处理
        if (prefix.empty() && suffix.empty()) return true; // p="*"
        if (s.empty()) return prefix.empty() && suffix.empty();
        
        // 在s中寻找匹配prefix的位置
        size_t prefix_match = s.find(prefix);
        if (prefix_match == string::npos) return false;
        
        // 在剩余部分中寻找匹配suffix的位置
        size_t start_search = prefix_match + prefix.length();
        if (start_search > s.length()) return suffix.empty();
        
        size_t suffix_match = s.rfind(suffix);
        if (suffix_match == string::npos) return false;
        
        // 检查后缀匹配是否在prefix匹配之后
        return (suffix_match >= start_search) && 
               (suffix_match + suffix.length() <= s.length());
    }
};

四、代码详解

1. ‌星号定位‌：

• 使用find()方法定位星号位置

• 将模式字符串分割为前缀和后缀

2. ‌特殊情况处理‌：

• 当p="*"时，可以匹配任何字符串

• 当s为空时，只有p="*"或空字符串才能匹配

3. ‌前缀匹配‌：

• 在s中查找前缀匹配的位置

• 如果找不到前缀匹配，直接返回false

4. ‌后缀匹配‌：

• 在前缀匹配后的剩余部分中反向查找后缀匹配

• 确保后缀匹配在前缀匹配之后

• 检查匹配边界是否合法

五、扩展思考

1. 如果模式字符串包含多个星号，算法该如何调整？

2. 如何修改算法来返回所有匹配的子串位置？

3. 如果星号只能匹配特定字符集合，算法该如何变化？

掌握这种带通配符的字符串匹配算法，能够帮助你解决许多实际开发中的文本处理问题！