#11928. 简单的通配符匹配
简单的通配符匹配
:简单的通配符匹配
时间限制:2秒 内存限制:1024MB
题目描述: 给定两个字符串 T
和 U
,其中字符串 T
包含字符和通配符 ?
,U
是一个普通字符串。T
中的 ?
可以匹配 U
中的任何字符。请判断 U
是否可以作为 T
的一个连续子串。
输入格式:
- 第一行包含字符串
T
,长度为n
(1 ≤ n ≤ 100)。 - 第二行包含字符串
U
,长度为m
(1 ≤ m ≤ n)。
输出格式:
- 输出 "Yes" 如果
U
能作为T
的一个连续子串;否则,输出 "No"。
示例输入:
a?c?b
acdb
示例输出:
Yes
解题思路:
- 遍历
T
中的每一个可能位置(从T[0]
到T[n - m]
),检查U
是否可以作为该位置开始的子串。 - 对于每个位置,逐字符比较:
- 如果
T[i + j]
不是?
,就要检查T[i + j]
是否和U[j]
相同。 - 如果是
?
,它可以匹配U[j]
中的任何字符。
- 如果
- 如果找到匹配的位置,输出 "Yes";如果遍历完成后没有找到匹配,输出 "No"。
示例 1:
T = "a?c?b"
U = "acdb"
输出:
Yes
解释:通过替换 T
中的 ?
,T
可以变成 acdb
,因此匹配成功。
示例 2:
T = "a?c?b"
U = "abc"
输出:
No
解释:没有可能的替换使得 T
可以变成 abc
,所以输出 No
。
示例 3:
T = "?ac?b"
U = "acdb"
输出:
Yes
解释:通过替换 ?
为 d
和 ?
为 b
,T
可以变成 acdb
,因此匹配成功。
示例 4:
T = "?????"
U = "acdb"
输出:
Yes
解释:T
中所有的 ?
可以替换成 acdb
,因此匹配成功。
示例 5:
T = "a?d?b"
U = "acdb"
输出:
Yes
解释:通过替换 T
中的 ?
,T
可以变成 acdb
,因此匹配成功。
示例 6:
T = "a?c?b"
U = "abc"
输出:
Yes
解释:通过替换 T
中的 ?
,T
可以变成 abc
,因此匹配成功。
示例 7:
T = "a?b?c"
U = "abc"
输出:
Yes
解释:通过替换 T
中的 ?
,T
可以变成 abc
,因此匹配成功。
示例 8:
T = "?b?b?"
U = "bdb"
输出:
Yes
解释:通过替换 T
中的 ?
,T
可以变成 bdb
,因此匹配成功。