力扣3407题解：利用星号通配符优化字符串匹配

一、题目解读

力扣3407题要求判断给定字符串s是否匹配模式串p，其中p允许包含通配符“”（匹配任意字符序列）。题目核心在于处理星号的灵活匹配规则，需考虑前后缀的组合匹配情况，同时避免无效匹配位置。理解“”的任意扩展特性是解题的关键。

二、解题思路

采用“分治+定位”策略：

1. 定位p中星号位置，将模式分为前后缀；

2. 优先匹配前缀在s中的首次出现位置；

3. 利用后缀在剩余子串中的逆序查找，确保匹配顺序正确；

4. 通过边界条件（如空串、仅星号）及位置验证规避无效情况。

此思路巧妙利用字符串查找函数（find/rfind），避免暴力匹配，提升效率。

三、解题步骤

1. 定位星号，分割模式：通过find获取星号索引，将p分为前缀（左侧）和后缀（右侧）。

2. 处理特殊边界：

○ 若p="*"，直接返回true（空串匹配）；

○ 若s为空，仅当p前后缀均为空才匹配。

3. 前缀匹配定位：在s中查找前缀首次出现位置（find），若不存在则失败。

4. 后缀逆序匹配：从匹配点后开始，逆序查找后缀（rfind），确保后缀在剩余部分末尾。

5. 验证位置合法性：检查后缀匹配是否在前缀之后且不越界，避免如“*ab”匹配“abab”的误判。

四、代码与注释

class Solution {  
public:  
    bool hasMatch(string s, string p) {  
        // 1. 定位星号，分割模式  
        size_t star_pos = p.find('*');  
        string prefix = p.substr(0, star_pos); // 星号前部分  
        string suffix = p.substr(star_pos + 1); // 星号后部分  
        
        // 2. 特殊边界处理  
        if (prefix.empty() && suffix.empty()) return true; // p="*"  
        if (s.empty()) return prefix.empty() && suffix.empty();  
        
        // 3. 查找前缀在s中的位置  
        size_t prefix_match = s.find(prefix);  
        if (prefix_match == string::npos) return false;  
        
        // 4. 剩余部分逆序查后缀  
        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;  
        
        // 5. 验证位置合法性  
        return (suffix_match >= start_search) &&  
               (suffix_match + suffix.length() <= s.length());  
    }  
};

通过精简的逻辑与原生函数（find/rfind）实现高效匹配，避免递归或复杂循环。

五、总结

本解法通过“分治定位+边界优化”思路，将星号匹配转化为前后缀的独立查找，结合位置验证确保匹配顺序正确。时间复杂度O(m+n)，适用于中等规模字符串场景。在工程应用中，该策略可扩展至文件检索、文本过滤等需通配符匹配的场景，兼具效率与实用性。