HJ71 字符串通配符

本节目标：理解“HJ71 字符串通配符”的核心思路，并能把它用于实际开发或面试表达。 中等 通过率：22.02% 时间限制：1秒 空间限制：32M 知识点==字符串== 描述 问题描述：在计算机中，通配符一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。现要求各位实现字符串通配符的算法。 要求： 实现如下2个通配符： ：匹配0个或以上的字符（注：能被和?匹配的字符仅由英文字母和数字0到9组成，下同） ？：匹配1个字符 注意：匹配时不区分大小写。 输入： 通配符表达式； 一组字符串。 输出： 返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false 数据范围：字符串长度：1≤�≤100 1≤s≤100 进阶：时间复杂度：�(�2) O(_n_2) ，空间复杂度：�(�) O(n) 输入描述： 先输入一个带有通配符的字符串，再输入一个需要匹配的字符串 输出描述： 返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false 示例1 输入： te?t*.txt12.xls ==复制== 输出： false ==复制== 示例2 输入： zzz ==复制== 输出： false ==复制== 示例3 输入： pqpppq ==复制== 输出： false ==复制== 示例4 输入： *Z0QZz ==复制== 输出： true ==复制== 示例5 输入： ?Bc?abcd ==复制== 输出： true ==复制== 示例6 输入： h?ah#a ==复制== 输出： false ==复制== 说明： 根据题目描述可知能被和?匹配的字符仅由英文字母和数字0到9组成，所以?不能匹配#，故输出false 示例7 输入： ppqp**pqpp*ppqpppppppqppqqppqppppqqqppqppqpqqqppqpqpppqpppqpqqqpqqp ==复制== 输出： false

这个问题是关于实现一个简化版的通配符匹配算法，它需要处理两种通配符：* 和 ?。* 可以匹配任意数量（包括零）的字符，而 ? 匹配恰好一个字符。这里提供的匹配算法是大小写不敏感的。

由于算法的复杂性主要来自于 * 通配符的存在，因此一个高效的方法是使用动态规划来解决这个问题。我们可以创建一个布尔型的二维数组 dp[i][j]，其中 dp[i][j] 表示通配符模式的前 i 个字符和字符串的前 j 个字符是否匹配。

算法步骤如下：

1. 初始化 dp[0][0] 为 true，因为两个空字符串是匹配的。
2. 对于模式 p 的第一个字符为 *，dp[1][0] 应为 true，因为 * 可以匹配空字符串。
3. 遍历模式 p 和字符串 s，根据当前字符更新 dp 表：

• 如果 p[i] 是 ? 或当前字符在 p 和 s 中匹配（考虑到大小写不敏感，需要转换为同一大小写进行比较），则 dp[i][j] = dp[i-1][j-1]。
• 如果 p[i] 是 *，则 dp[i][j] = dp[i-1][j] || dp[i][j-1]。这表示 * 要么匹配 s 中的当前字符（dp[i][j-1]），要么不匹配任何字符（dp[i-1][j]）。

4. 最终的匹配结果是 dp[p.length][s.length]。

下面是实现这个算法的 Python 代码示例：

def isMatch(s, p): s, p = s.lower(), p.lower() # 转换为小写以进行大小写不敏感的比较 dp = [[False] * (len(s) + 1) for _ in range(len(p) + 1)] dp[0][0] = True for i in range(1, len(p) + 1): if p[i-1] == '': dp[i][0] = dp[i-1][0] else: break def isAlphanumeric(c): return c.isalnum() # 检查c是否为英文字母或数字 for i in range(1, len(p) + 1): for j in range(1, len(s) + 1): if p[i-1] == '': dp[i][j] = dp[i-1][j] or dp[i][j-1] elif p[i-1] == '?' and isAlphanumeric(s[j-1]): dp[i][j] = dp[i-1][j-1] elif p[i-1] == s[j-1]: dp[i][j] = dp[i-1][j-1] return dp[len(p)][len(s)]

while True: try: pattern = input() string = input() print(str(isMatch(string, pattern)).lower()) except EOFError: break

这段代码首先处理了一些边界条件，比如两个空字符串的匹配以及模式字符串以一个或多个 * 开头的情况。然后，它通过双重循环遍历字符串和模式，使用动态规划的方法填充 dp 表，最后根据 dp 表的最后一个元素返回匹配结果。