刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

2.通配符匹配
给定一个字符串s和一个字符模式p,请实现一个支持'?'和'*'的通配符匹配功能。
其中‘?’可以匹配任何单个字符,如‘a?c’可以成功匹配‘aac’,‘abc’等字符串,但不可匹配‘ac’,‘aaac’等字符串 。
‘*’ 可以匹配任意长度字符串(包括空字符串),如‘a*c’可以成功匹配‘ac’,‘abdc’,‘abc’,‘aaac’等字符串,但不可匹配‘acb’,‘cac’等字符串。
两个字符串完全匹配才算匹配成功。
时间限制:2000
内存限制:262144
输入
输入为一个数字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
```

使用微信搜索喵呜刷题,轻松应对考试!

答案:

解析:

【喵呜刷题小喵解析】本题是一道经典的动态规划问题,可以使用动态规划算法来解决。首先,我们定义一个二维数组dp,其中dp[i][j]表示字符串s的前i个字符和字符串p的前j个字符是否匹配。然后,我们根据题目中给出的通配符匹配规则,进行状态转移。对于字符串p的第j个字符,如果它是‘?’,则可以匹配字符串s的第i个字符,此时dp[i][j] = dp[i-1][j-1]。如果字符串p的第j个字符是‘*’,则可以匹配字符串s的第i个字符,也可以不匹配,此时dp[i][j] = dp[i-1][j] or dp[i][j-1]。最后,返回dp[m][n],其中m和n分别是字符串s和p的长度。在代码中,我们使用了动态规划的思想,通过状态转移方程,逐步计算出dp数组的值,最终得到结果。需要注意的是,对于字符串p的第0个字符,即空字符串,我们需要单独处理。当字符串p的第0个字符是‘*’时,它可以匹配字符串s的任意前缀,因此dp[0][j] = dp[0][j-1]。在输入部分,我们使用input()函数从标准输入中读取输入数据,并进行处理。在输出部分,我们使用print()函数将结果输出到标准输出中。
创作类型:
原创

本文链接:2.通配符匹配给定一个字符串s和一个字符模式p,请实现一个支持'?'和'*'的通配符匹配功能。其中‘

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share