我要招人

去企业版

首页 > 试题广场 >

通配符匹配

[编程题]通配符匹配

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

请实现支持'?'and'*'.的通配符模式匹配

'?' 可以匹配任何单个字符。
'*' 可以匹配任何字符序列（包括空序列）。

返回两个字符串是否匹配

函数声明为：

bool isMatch(string s,string p)

下面给出一些样例：

isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "d*a*b") → false

数据范围：字符串长度满足 $0 \le n \le 1000$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

"ab","?*"

输出

true

示例2

输入

"ab","*"

输出

true

算法知识视频讲解

未来0116

发表于 2021-07-11 17:11:43

精华题解一.题目描述NC44通配符匹配题目链接：https://www.nowcoder.com/practice/e96f1a44d4e44d9ab6289ee080099322tpId=196&&tqId=37075&rp=1&ru=/activity/oj&qr 展开全文

牛一霸

发表于 2021-07-14 22:20:39

精华题解题目：通配符匹配描述：请实现支持'?'and'*'.的通配符模式匹配 '?'可以匹配任何单个字符。 '*'可以匹配任何字符序列（包括空序列）。返回两个字符串是否匹配函数声明为：bool isMatch(const char *s, const char *p) 下展开全文

牛客786963925号

发表于 2021-07-17 17:53:17

精华题解解法一：动态规划由于此题中"*"可以匹配多个字符（包括空字符），因此枚举所有可能性较为麻烦，一种简单的思路是采用动态规划算法进行求解，具体思路如下：定义动态规划数组dp，其中dp[i] [j]表示「s字符串的前i个字符与p字符串的前j个字符是否匹配」。而对于每个位置，有如下三展开全文

堆栈哲学

发表于 2021-07-15 12:29:46

精华题解解法一：贪心如果i和j标记的字符正好相等或者j字符是'?'匹配成功，则"移除"i和j元素，即自增i、j。否则如果j字符是✳(*号)依然可以匹配成功，则用istart和jstart分别标记i元素和j元素之后自增j。否则如果istart>-1说明之前匹配过✳，因为✳可以匹展开全文

蒙牛麦片

发表于 2021-07-16 22:23:52

精华题解 NC44 通配符匹配题意分析：给定字符串S，模式串P，判断S是否能够被P所匹配，通配符只有？和*，？可以匹配任意一个字符，*可以匹配任意长度的字符串题解一（动态规划）：设置表示字符串S的(0-i)部分是否被字符串P的(0-j)部分匹配初始化：，字符串s的(0-0)为空，那么只要字符串P 展开全文

LifelongCode

发表于 2021-06-04 15:12:02

思路1：动态规划在给定的模式 p 中，只会有三种类型的字符出现：小写字母 a-z，可以匹配对应的一个小写字母；问号 ?，可以匹配任意一个小写字母；星号 *∗，可以匹配任意字符串，可以为空，也就是匹配零或任意多个小写字母其中「小写字母」和「问号」的匹配是确定的，而「星号」的匹配是不确定的，因展开全文

华科不平凡

发表于 2020-08-31 16:04:43

为了描述方便，我们将s称为主串，p称为模式串三种思路：贪心（超时）回溯动态规划贪心（超时） // // Created by jt on 2020/8/31. // #include <cstring> #include <iostream> using na 展开全文

Ruoji55555

发表于 2021-03-14 11:11:05

主要是对*的处理，并且这里的*和传统正则的*还不太一样 public boolean isMatch(String s, String p) { char[] str= s.toCharArray(); char[] ptr= p.toCharArray( 展开全文

宫水三叶的刷题日记

发表于 2021-08-26 16:08:31

动态规划整理一下题意，对于字符串 p 而言，有三种字符：普通字符：需要和 s 中同一位置的字符完全匹配 '?'：能够匹配 s 中同一位置的任意字符 '*'：能够匹配任意字符串所以本题关键是分析当出现 '*' 这种字符时，是匹配 0 个字符、还是 1 个字符、还是 2 个字符 ... 展开全文

认认真真coding

发表于 2022-01-30 15:12:21

通配符匹配 1、题意重述请实现支持'?'and'*'的通配符模式匹配 '?' 可以匹配任何单个字符。 '*' 可以匹配任何字符序列（包括空序列）。换句话说，就是使？能够等于任何一个字符，*能够等于任何一个字符序列。 2、思路整理使用贪心的思想： Step1:对于两个字符串，我们用i和j分别标记展开全文