[C++知识库]【每日一题】字符串通配符

问题描述：在计算机中，通配符一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。现要求各位实现字符串通配符的算法。
要求：
实现如下2个通配符：
：匹配0个或以上的字符（注：能被和?匹配的字符仅由英文字母和数字0到9组成，下同）
？：匹配1个字符

注意：匹配时不区分大小写。

输入：
通配符表达式；
一组字符串。

输出：
返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
数据范围：字符串长度：1\le s\le 100\1≤s≤100
进阶：时间复杂度：O(n^2)\O(n
2
) ，空间复杂度：O(n)\O(n)

#include <iostream>
#include <vector>
using namespace std;

//由于这两个字符串都不需要修改，使用const
bool match(const char* pattern, const char* str) {
	//这么匹配通配符我们用递归来做
	//递归我们先来想一下结束条件

	//1. 如果都到了\0，条件满足
	if (*pattern == '\0' && *str == '\0') return true;
	//2. 如果有一方先为\0，另一方不满足
	if (*pattern == '\0' || *str == '\0') return false;
	//3. 第三种情况继续判断
	//如果匹配到星号 * 
	//分三种情况，只要满足任意一种即可： 
	//3.1 pattern向后走(没有匹配到为0个)，str不动
	//3.2 pattern和str一起走(匹配到一个)
	//3.3 pattern不动，str匹配到多个。
	if (*pattern == '*') {
		return match(pattern + 1, str) || match(pattern + 1, str + 1) || match(pattern, str + 1);
	}
	else if (*pattern == '?') {
		return match(pattern + 1, str + 1);
	}
	else if (*pattern == *str) {
		return match(pattern + 1, str + 1);
	}
	return false;
}

int main() {

	string pattern, str;
	while (cin >> pattern >> str) {
		bool ret = match(pattern.c_str(), str.c_str());
		if (ret) {
			cout << "true" << endl;
		}
		else {
			cout << "false" << endl;
		}
	}

}

Nowcoder Link：
https://www.nowcoder.com/questionTerminal/43072d50a6eb44d2a6c816a283b02036