首页 > 试题广场 >

字符串模式匹配

[编程题]字符串模式匹配

热度指数：2315 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出两个字符串，分别是模式串P和目标串T，判断模式串和目标串是否匹配，匹配输出 1，不匹配输出 0。模式串中‘？’可以匹配目标串中的任何字符，模式串中的 ’*’可以匹配目标串中的任何长度的串，模式串的其它字符必须和目标串的字符匹配。例如P=a?b，T=acb，则P 和 T 匹配。

输入描述:

输入第一行包含一个字符串p， (1 ≤ |p| ≤ 20).
输入第二行包含一个字符串t， (1 ≤ |t| ≤ 20).

输出描述:

输出仅包含0和1的整数，0表示p和t不匹配，1表示p和t匹配。

示例1

输入

a?b
ab

输出

示例2

输入

a*b
ab

输出

示例3

输入

a*b
a(cb

输出

备注:

保证T中不包含 ‘*’ 字符和 ‘?’ 字符

算法知识视频讲解

Python

小橙子&

p = input().strip()
t = input().strip()
def DFS(p,t,i,j):
    if i == len(p) and j == len(t):
        return True
    if i == len(p):
        return False
    if j == len(t):
        return False
    if p[i] not in ['*','?']:
        if p[i] != t[j]:
            return False
        else:
            if DFS(p,t,i+1,j+1):
                return True
    else:
        if p[i] == '*':
            if DFS(p,t,i,j+1)&nbs***bsp;DFS(p,t,i+1,j+1)&nbs***bsp;DFS(p,t,i+1,j):
                return True
        else:
            if DFS(p,t,i+1,j+1):
                return True
if DFS(p,t,0,0):
    print(1)
else:
    print(0)

发表于 2020-08-22 16:22:46 回复(0)