C++算法 通配符匹配

LeetCode44题目

给你一个输入字符串 (s) 和一个字符模式 § ，请你实现一个支持 ‘?’ 和 ‘’ 匹配规则的通配符匹配：
‘?’ 可以匹配任何单个字符。
'’ 可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

示例 1：
输入：s = “aa”, p = “a”
输出：false
解释：“a” 无法匹配 “aa” 整个字符串。
示例 2：
输入：s = “aa”, p = ""
输出：true
解释：'’ 可以匹配任意字符串。
示例 3：
输入：s = “cb”, p = “?a”
输出：false
解释：‘?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。

2022年12月

class Solution {
public:
bool isMatch(string s, string p) {
unordered_set preDp;
preDp.insert(0);
for (const auto& ch : p )
{
unordered_set dp;
if (‘*’ == ch)
{
int iMin = *std::min_element(preDp.begin(), preDp.end());
for (; iMin <= s.length(); iMin++)
{
dp.insert(iMin);
}
}
else
{
for (const auto& pre : preDp)
{
if (pre < s.length())
{
if ((‘?’ == ch) || (ch == s[pre]))
{
dp.insert(pre + 1);
}
}
}
}

		 preDp.swap(dp);
		 if (preDp.empty())
		 {
			 return false;
		 }
	 }
	 return *std::max_element(preDp.begin(),preDp.end()) >= s.length();
 }
1
2
3
4
5
6
7
8

};

2023年8月

class Solution {
public:
bool isMatch(string s, string p) {
if (p.empty())
{
return s.empty();
}
vector vp;
int left = 0;
for (int i = 0; i < p.length()😉
{
while ((i < p.length()) && (‘’ != p[i]))
{
i++;
}
//p[i]为’\0’或
vp.emplace_back(p.substr(left, i - left));
while ((i < p.length()) && (’’ == p[i]))
{
i++;
}
left = i;
}
if ('’ == p.back())
{
vp.emplace_back(“”);
}
if (1 == vp.size())
{
return (s.length()p.length())&& (0Cmp(s,p));
}
const int iFirstLen = vp.front().length();
if (s.length() < iFirstLen)
{
return false;
}
if (0 != Cmp( s, vp.front()))
{
return false;
}
s = s.substr(iFirstLen);
vp.erase(vp.begin(), vp.begin()+1);

	const int iRemain = s.length() - vp.back().length();
	if (iRemain < 0)
	{
		return false;
	}
	if (0 != Cmp(s.substr(iRemain), vp.back()))
	{
		return false;
	}
	s = s.substr(0, iRemain);
	vp.pop_back();

	for (const auto& subP : vp)
	{
		const int ind = Cmp(s, subP);
		if (-1 == ind)
		{
			return false;
		}
		s = s.substr(ind + subP.length());
	}
	return true;
}

int Cmp( const string& s , const string& strP)
{
	int len = strP.length();
	for (int i = 0; i+len <= s.length(); i++)
	{
		if (CmpInner(s, i, strP))
		{
			return i;
		}
	}		
	return -1;
}
bool CmpInner(const string& s,int si, const string& strP)
{
	int len = strP.length();
	for (int i = 0; i < len; i++)
	{
		if ((s[i+si] != strP[i]) && ('?' != strP[i]))
		{
			return false;
		}
	}
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

};

其它

视频课程

如果你觉得复杂，想从简单的算法开始，可以学习我的视频课程。
https://edu.csdn.net/course/detail/38771
我的其它课程
https://edu.csdn.net/lecturer/6176

测试环境

win7 VS2019 C++17

相关下载

doc版文档，排版好
https://download.csdn.net/download/he_zhidan/88348653