题解 | #字符串通配符#

解题思路

1. 题目要求：

   • 实现通配符匹配
   • '*' 匹配0个或以上的字符
   • '?' 匹配1个字符
   • 不区分大小写
   • 字符串长度

2. 解题方法：递归

   • 从后向前匹配字符
   • 分三种情况处理：
     1. 字符相等或遇到'?'时，递归匹配剩余部分
     2. 遇到'*'时，尝试匹配0个或多个字符
     3. 其他情况表示不匹配

代码

def fun(str1, str2):
    # 两个字符串都为空，匹配成功
    if str1 == '' and str2 == '':
        return True
    # 模式串为空，字符串不为空，匹配失败
    elif str1 == '' and str2 != '':
        return False
    # 模式串不为空，字符串为空，只有模式串全为*才匹配成功
    elif str1 != '' and str2 == '':
        if str1.replace('*', '') == '':
            return True
        else:
            return False
    else:
        m, n = len(str1), len(str2)
        # 字符相等或是?且字符串为字母数字
        if str1[m-1] == str2[n-1] or (str1[m-1] == '?' and str2[n-1].isalnum()):
            return fun(str1[:m-1], str2[:n-1])
        # 遇到*号，可以匹配0个或多个字符
        elif str1[m-1] == '*':
            return fun(str1[:m-1], str2) or fun(str1, str2[:n-1])
        else:
            return False

while True:
    try:
        str1, str2 = input().lower(), input().lower()
        print('true' if fun(str1, str2) else 'false')
    except:
        break

import java.util.*;

public class Main {
    public static boolean fun(String str1, String str2) {
        // 两个字符串都为空，匹配成功
        if (str1.isEmpty() && str2.isEmpty()) {
            return true;
        }
        // 模式串为空，字符串不为空，匹配失败
        else if (str1.isEmpty() && !str2.isEmpty()) {
            return false;
        }
        // 模式串不为空，字符串为空，只有模式串全为*才匹配成功
        else if (!str1.isEmpty() && str2.isEmpty()) {
            return str1.replace("*", "").isEmpty();
        }
        else {
            int m = str1.length(), n = str2.length();
            char last1 = str1.charAt(m-1);
            char last2 = str2.charAt(n-1);
            
            // 字符相等或是?且字符串为字母数字
            if (last1 == last2 || (last1 == '?' && Character.isLetterOrDigit(last2))) {
                return fun(str1.substring(0, m-1), str2.substring(0, n-1));
            }
            // 遇到*号，可以匹配0个或多个字符
            else if (last1 == '*') {
                return fun(str1.substring(0, m-1), str2) || 
                       fun(str1, str2.substring(0, n-1));
            }
            else {
                return false;
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str1 = sc.nextLine().toLowerCase();
            String str2 = sc.nextLine().toLowerCase();
            System.out.println(fun(str1, str2) ? "true" : "false");
        }
    }
}

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

bool fun(string str1, string str2) {
    // 两个字符串都为空，匹配成功
    if (str1.empty() && str2.empty()) {
        return true;
    }
    // 模式串为空，字符串不为空，匹配失败
    else if (str1.empty() && !str2.empty()) {
        return false;
    }
    // 模式串不为空，字符串为空，只有模式串全为*才匹配成功
    else if (!str1.empty() && str2.empty()) {
        string temp = str1;
        temp.erase(remove(temp.begin(), temp.end(), '*'), temp.end());
        return temp.empty();
    }
    else {
        int m = str1.length(), n = str2.length();
        char last1 = str1[m-1];
        char last2 = str2[n-1];
        
        // 字符相等或是?且字符串为字母数字
        if (last1 == last2 || (last1 == '?' && isalnum(last2))) {
            return fun(str1.substr(0, m-1), str2.substr(0, n-1));
        }
        // 遇到*号，可以匹配0个或多个字符
        else if (last1 == '*') {
            return fun(str1.substr(0, m-1), str2) || 
                   fun(str1, str2.substr(0, n-1));
        }
        else {
            return false;
        }
    }
}

int main() {
    string str1, str2;
    while (getline(cin, str1) && getline(cin, str2)) {
        transform(str1.begin(), str1.end(), str1.begin(), ::tolower);
        transform(str2.begin(), str2.end(), str2.begin(), ::tolower);
        cout << (fun(str1, str2) ? "true" : "false") << endl;
    }
    return 0;
}

算法分析

• 算法：递归
• 时间复杂度：，其中 为字符串长度
• 空间复杂度：，递归调用栈的深度