#11928. 简单的通配符匹配

简单的通配符匹配

简单的通配符匹配

时间限制​:2秒 ​内存限制​:1024MB

题目描述​: 给定两个字符串 TU,其中字符串 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?bT 可以变成 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,因此匹配成功。