【华为OD机试真题】字符串通配符(200分)

题目

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M

在计算机中，通配符是一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。现要求实现字符串通配符的算法。

要求：
实现如下2个通配符：
* : 匹配0个或以上的字符（注：能被*和?匹配的字符仅由英文字母和数字0到9组成，下同）
?: 匹配1个字符
注意：匹配时不区分大小写。

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

输出:
返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
数据范围：字符串长度：1 ≤ s ≤ 100

进阶：时间复杂度：O(n²) ，空间复杂度：O(n)

输入描述

先输入一个带有通配符的字符串，再输入一个需要匹配的字符串

输出描述

返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false

示例1

输入
te?t*.*
txt12.xls
输出
false

示例2

输入
?*Bc*?
abcd
输出
true

示例3

输入
p*p*qp**pq*p**p***ppq
pppppppqppqqppqppppqqqppqppqpqqqppqpqpppqpppqpqqqpqqp
输出
false

本题可在牛客网练习：字符串通配符

个人解法

提示：个人学习,并非最优解,欢迎指正

正则解法：实际答题时，本题如果使用正则全匹配（即代码中注释的一行），或者使用fullmath(), 容易在示例3用例处超时2s,不能通过全部用例. 所以本题改成用findall()，然后判断str2是否在匹配的结果列表中。

import re
while True:
    try:
        str1 = input().strip().lower()
        str2 = input().strip().lower()
        str1 = str1.replace(".", "\.").replace("*", "[a-z0-9]*").replace("?", "[a-z0-9]{1}")
        #str1 = f"^{str1}$"
        if str2 in re.findall(str1,str2):
            print("true")
        else:
            print("false")
    except:
        break

总结

需要注意的地方:

1. 此题的*和?跟re模块正则的匹配范围不一致,限定了[a-z0-9]的范围和匹配的数量,所以要特别注意;
2. 另外此题的.号等也不是re里面的通配符,所以需要转义(其实很多其他符号应该也需要转义,但是本题用例不涉及所以没有写)

系列文章目录

系列文章
【华为OD机试真题】字符串通配符