题目描述

首先我们有两个字符串，第一个字符串是我们的$s1s1$这个里面是含有我们的匹配符号的，然后第二个字符串是我们的$s2s2$这个里面是没有匹配符号的，我们需要判断我们的$s1s1$是否可以正好匹配$s2s2$

规则如下：

• 如果是*号我们可以匹配0，1，多个字符
• 如果是？号我们只可以匹配一个字符
• 我们*和？匹配的只能是字母或者是数字
• 匹配时不区分大小写

题解

解法一：还是取巧的做法

实现思路

事实上这个题目，我们完全可以用正则表达式给过掉，首先我们可以先把我们的两个字符串都变成小写，然后分别对应我们的一个匹配规则，然后最后查看是否可以完全匹配即可

代码实现

from re import *

while True:
    try:
        s1 = input().lower()
        s2 = input().lower()
        # 把我们的两个字符串输入，并以小写字母的形式存储

        s1 = s1.replace('.', '\.').replace('?', '[a-z0-9]{1}').replace('*', "[a-z0-9]*")
        # 定义我们的正则表达式的匹配规则

        if s2 in findall(s1, s2):
            # 这个看我们的带有通配符的字符串是否可以完全匹配我们的模式串
            print("true")
        else:
            print("false")
    except:
        break

时空复杂度分析

时间复杂度： $O(n)O(n)$

理由如下：我们需要把我们输入的两个字符串全部小写，然后我们需要去构建我们的正则，然后匹配

空间复杂度： $O(1)O(1)$

理由如下：我们未使用额外的空间

解法二：

实现思路

我们很容易可以想到的就是我们的搜索，然后我们这里讲解一下我们搜索的一个思路

这里我们用$ll$表示我们$s1s1$字符串到了哪一个位置，我们用$rr$表示我们的$s2s2$字符串到了哪一个位置

然后我们就可以得到我们以下的一些推导

1. 如果我们当前的$s1[l]==s2[r]s1[l]\; ==\; s2[r]$

那么我们就会让我们的$l=l+1,r=r+1l\; =\; l\; +\; 1,\; r\; =\; r\; +\; 1$

2. 如果我们当前的$s1[l]==?s1[l]\; ==\; ?$，我们可以判断我们当前的这位$s2[r]s2[r]$是否满足条件，就是他是否只是字母和数字，如果不是返回$falsefalse$，否则我们让$l+=1,r+=1l\; +=\; 1,\; r\; +=\; 1$

3. 如果我们当前的$s1[l]==\ast s1[l]\; ==\; *$，我们可以考虑，我们现在可以匹配空字符串，那么我们就是$l+=1l\; +=\; 1$，然后我们可以考虑匹配一个字符串，那么我们本质其实就是跟我们为$??$的情况一致了，然后如果我们匹配多个字符串，那么我们就是可以递归的判断$r+=1r\; +=\; 1$

接下来我们把我们的思路转换为我们的代码实现

图解代码

代码实现

#include <bits/stdc++.h>

using namespace std;

bool dfs(const string &s1, const string &s2, int l, int r) {
    if (l == s1.size() && r == s2.size()) return true;
    if (l == s1.size()) return false;
    // 这个是我们的带有匹配字符的字符串到了结束的位置
    if (r == s2.size()) {
        // 如果我们的匹配字符串到了我们结束的位置
        // 事实上如果我们带有匹配字符的字符串后面都是*也是可以的
        for (int i = l; i < s1.size(); i++) {
            if (s1[i] != '*') return false;
        }
        return true;
    }
    if (tolower(s1[l]) == tolower(s2[r])) {
        // 如果我们当前的位置是匹配的
        return dfs(s1, s2, l + 1, r + 1);
    } else if (s1[l] == '?') {
        if (isdigit(s2[r]) || islower(s2[r]) || isupper(s2[r])) {
            // 如果我们的这一个位置是字母或者是数字，我们直接递归
            return dfs(s1, s2, l + 1, r + 1); 
        } else {
            // 如果不是的话，我们直接返回false
            return false;
        }
    } else if (s1[l] == '*') {
        // 如果遇到多个星号，我们只需要匹配一个
        while (s1[l] == '*') ++l;
        --l;
        return dfs(s1, s2, l, r + 1) || dfs(s1, s2, l + 1, r + 1) || dfs(s1, s2, l + 1, r);
    }
    return false;
}


signed main() {
    string s1, s2;
    cin >> s1 >> s2;
    // 这个s1就是我们带有通配符的字符串
    // 这个s2就是我们要去匹配的字符串
    bool okk = dfs(s1, s2, 0, 0);
    okk ? cout << "true\n" : cout << "false\n";
    return 0;
}

时空复杂度分析

时间复杂度： $O(2^n)O(2\; ^\; n)$

理由如下：我们遇到这种问题的时候，我们可以画一颗搜索树，就是从根节点开始，把他的所有可能都给列举出来，我们其实可以发现，他这个就是一个树形的结构，所以我们的时间复杂度是$O(2^n)O(2\; ^\; n)$，可能有的同学会疑惑为什么不是$O(3^n)O(3\; ^\; n)$，大家可以仔细想一下，我们在过程中把很多个*号合并为一个，所以事实上我们是泡不到$O(3^n)O(3\; ^\; n)$的

空间复杂度： $O(n)O(n)$

理由如下：事实上我们只是需要考虑我们的系统的递归栈的深度，那么我们系统递归栈的深度是多少呢，事实上我们最多把我们所有位置走一遍，那么我们最深也就是$nn$，所以我们的时间复杂度就是$O(n)O(n)$的