力扣3407题解：利用星号通配符优化字符串匹配
20小时前
一、题目解读
力扣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)，适用于中等规模字符串场景。在工程应用中，该策略可扩展至文件检索、文本过滤等需通配符匹配的场景，兼具效率与实用性。
原创内容 转载请注明出处
