24834: 通配符匹配

string, re, dp, http://cs101.openjudge.cn/practice/24834/

给定一个字符串s和一个字符模式p，请实现一个支持'?'和'*'的通配符匹配功能。

其中‘?’可以匹配任何单个字符，如‘a?c’可以成功匹配‘aac’,‘abc’等字符串，但不可匹配‘ac’,‘aaac’等字符串。

‘*’ 可以匹配任意长度字符串（包括空字符串）,如‘a*c’可以成功匹配‘ac’,‘abdc’,‘abc’,‘aaac’等字符串，但不可匹配‘acb’，‘cac’等字符串。

两个字符串完全匹配才算匹配成功。

输入

输入为一个数字n表示测试字符串与字符模式对数，换行。(n ≤ 30) 后续2n行为每组匹配的s与p，每行字符串后换行。 s 非空，只包含从 a-z 的小写字母。 p 非空，只包含从 a-z 的小写字母，以及字符 ? 和 *。字符串s和p的长度均小于50

输出

每一组匹配串匹配成功输出‘yes’,否则输出‘no’。

样例输入

3
abc
abc
abc
a*c
abc
a??c

样例输出

yes
yes
no

Regular expression相关题目:

04015: 邮箱验证，24834:通配符匹配，

CF58A. Chat room, https://codeforces.com/problemset/problem/58/A

LeetCode 65. 有效数字，https://leetcode.cn/problems/valid-number/description/

Regulex 正则表达式在线测试工具，https://regex101.com

python

#23n2300017735(夏天明BrightSummer)
import re

for i in range(int(input())):
    s, p = input(), input().replace("?", ".{1}").replace("*", ".*") + "$"
    print("yes" if re.match(p, s) else "no")

这段代码是解决“通配符匹配”问题的动态规划解法。该问题的描述是，给定一个字符串s和一个包含一些通配符的模式串p，问是否能将s通过p匹配出来。

通配符包含以下两种：

? 可以匹配任何单个字符。

* 可以匹配任何字符序列（包括空序列）。代码中的dp[i][j]代表的是s的前i个字符和p的前j个字符是否能匹配。

初始化时，dp[0][0]设为True，表示两个空字符串是可以匹配的。然后，代码处理了模式串p的前j个字符和空字符串的匹配问题。如果p的第j个字符是*，则dp[0][j]应该等于dp[0][j-1]，表示*能匹配空字符串。

之后，代码对s的每一个字符和p的每一个字符进行判断。如果p的字符等于s的字符，或者p的字符为?，那么dp[i][j]的取值应该和dp[i-1][j-1]一样（即上一个字符的判断结果）。

如果p的字符为*，表示它可以匹配任意长度的字符序列，所以dp[i][j]取决于s[i]是否被*匹配，或者*是否为空字符串。即dp[i][j]应该等于dp[i-1][j]（忽略*的字符，即把*看作条无字符）和dp[i][j-1]之中的任意一个（忽略s中的当前字符，即把s的第i个字符纳入*的范围内）。

最后，打印出s长度为m，模式串p长度为n时对应的结果，如果为True则输出'yes'，否则输出'no'，表示s和p是否可以完全匹配。

python

# 蒋子轩23工学院
n = int(input())
for _ in range(n):
    s = input()
    p = input()
    m, n = len(s), len(p)
    #dp[i][j]为s的前i项和p的前j项能否匹配
    dp = [[False]*(n+1) for _ in range(m+1)]
    dp[0][0] = True
    #初始化s为空的情形
    for j in range(1, n+1):
        if p[j-1] == '*':
            dp[0][j] = dp[0][j-1]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if p[j-1] == '?' or p[j-1] == s[i-1]:
                dp[i][j] = dp[i-1][j-1]
            #'*'可指代空或任何长度字符
            elif p[j-1] == '*':
                dp[i][j] = dp[i-1][j] or dp[i][j-1]
    print('yes' if dp[m][n] else 'no')

24834: 通配符匹配 ​

24834: 通配符匹配