2025年LeetCode-----第四十四题-----通配符匹配

大家好，我是讯享网，很高兴认识大家。

通配符匹配

难度困难368

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

'?' 可以匹配任何单个字符。 '*' 可以匹配任意字符串（包括空字符串）。

讯享网

两个字符串完全匹配才算匹配成功。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

示例 1:

讯享网输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入: s = "aa" p = "*" 输出: true 解释: '*' 可以匹配任意字符串。

示例 3:

讯享网输入: s = "cb" p = "?a" 输出: false 解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

示例 4:

输入: s = "adceb" p = "*a*b" 输出: true 解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

示例 5:

讯享网

讯享网输入: s = "acdcb" p = "a*c?b" 输出: false

题目分析：

这里本来打算用递归，类似于剑指offer中的“正则表达式”。这里主要分为以下几种情况。难点主要集中在存在‘*’的情况下，这么去分析。原本打算使用for循环在递归中挨个遍历进行实现，发现不行，这个实现方式与想法相悖。它是需要‘*’后面几个字符与s字符串中的字符相匹配的，类似于s字符串为“abcabcabc”，p字符串为“a*abc”。那么p字符串的abc必须与s字符串中的最后的abc相匹配，所以使用for循环不行。

参考大神的题解，使用了双指针和贪心算法。连接：https://leetcode-cn.com/problems/wildcard-matching/solution/44-tong-pei-fu-pi-pei-shuang-zhi-zhen-by-guohaodin/

参考代码：（递归超时）

class Solution { public: bool isMatch(string s, string p) { if(s.empty() && p.empty()) return true; if(!s.empty() && p.empty()) return false; if(p[0] != '*') { if(s[0] == p[0] || !s.empty() && p[0] == '?') return isMatch(s.substr(1),p.substr(1)); else return false; }else{ if (!s.empty()) return isMatch(s.substr(1),p.substr(1)) || isMatch(s.substr(1),p)||isMatch(s,p.substr(1)); else return isMatch(s,p.substr(1)); } } };

参考代码：（DP）

参考代码：（双指针加贪心算法）

讯享网#include <iostream> #include <vector> #include <string> #include <unordered_map> #include <deque> #include <stack> #include <algorithm> #include <map> using namespace std; //如果s和p中字符匹配，则分别自增i和j //否则如果p中当前字符为星号，则标记iStar和jStar，同时自增j //否则如果iStar >= 0，表示之前匹配过星号，因为星号可以匹配任意字符串，所以继续递增i，同时移动j为jStar下一个字符 //否则返回false class Solution { public: bool isMatch(string s, string p) { //i为s的指针，j为p的指针 //iStar记录当p中遇到‘*’时，当前i位置 //jStar记录当p中遇到‘*’时，当前j位置 int i = 0, j = 0, iStar = -1, jStar = -1, m = s.size(), n = p.size(); //以i指针未到m为条件 while (i < m) { //如果当前字符匹配或者p[j]为？时都匹配，两个指针指向下一个字符 if (j < n && (s[i] == p[j] || p[j] == '?')) { ++i; ++j; }//判断p[j]为 '*'的情况，使用iStar记录i的位置，jStar记录j的位置，i不动，j往后移动来匹配当前i else if (j < n && p[j] == '*') { iStar = i; jStar = j++; }//如果匹配 '*'后面不成功，那么iStar向后移动位置，j重置到'*'的下一个字符 else if (iStar >= 0) { i = ++iStar; j = jStar + 1; }//其他情况都返回false else return false; } //如果j后面还有'*'，就都删除 while (j < n && p[j] == '*') ++j; return j == n; } }; int main() { Solution solution; string num1 = "adceb"; string num2 = "*a*b"; if (solution.isMatch(num1, num2)) cout << "yes" << endl; else cout << "no" << endl; system("pause"); return 0; }

2025年LeetCode-----第四十四题-----通配符匹配

相关推荐