我要招人

去企业版

首页 > 试题广场 >

正则表达式匹配

[编程题]正则表达式匹配

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

请实现一个函数用来匹配包括'.'和'*'的正则表达式。

1.模式中的字符'.'表示任意一个字符

2.模式中的字符'*'表示它前面的字符可以出现任意次（包含0次）。

在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配

数据范围:

1.str 只包含从 a-z 的小写字母。

2.pattern 只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。

3. $0 \le str.length \le 26 \$
4. $0 \le pattern.length \le 26 \$

示例1

输入

"aaa","a*a"

输出

true

说明

中间的*可以出现任意次的a，所以可以出现1次a，能匹配上

示例2

输入

"aad","c*a*d"

输出

true

说明

因为这里 c 为 0 个，a被重复一次， * 表示零个或多个a。因此可以匹配字符串 "aad"。

示例3

输入

"a",".*"

输出

true

说明

".*" 表示可匹配零个或多个（'*'）任意字符（'.'）

示例4

输入

"aaab","a*a*a*c"

输出

false

算法知识视频讲解

不是江小白

发表于 2021-07-05 02:43:25

精华题解 1. 解题前的思考一开始拿到这题，其实还挺懵逼的。🤣如果这题没有 ‘*’ （后面统一称呼为"星号”）这个字符在正则表达式中，这题将会简单点，我们只需要从左往右遍历字符串看是否能跟模式 '.' 匹配上即可。无星号的正则表达式匹配代码部分： def match(self, str, 展开全文

Maokt

发表于 2021-06-29 10:01:20

精华题解算法思想一：递归解题思路：每次从字符串里取出一个字符与模式中的字符匹配，如果模式中的字符是‘.’，它可以匹配字符串中的任意字符，如果不是，那么如果它与字符串中的字符相等则匹配。当字符串的字符和模式的字符匹配时，接着匹配后面的字符。下面，考虑模式中的第二个字符是不是‘*’。如果不是，展开全文

牛客题解官

发表于 2022-04-22 12:51:13

精华题解题目主要信息: 一个正常字符串str，可能为空，只包含小写字母一个模式串pattern，可能为空，只包含小写字母和‘*’与‘.’ 模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）求str与pattern是否能完全匹配举一反三：学习完本题的思路你可以解展开全文

江南好___

发表于 2021-07-04 02:04:06

精华题解描述题目描述请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab 展开全文

宫水三叶的刷题日记

发表于 2021-07-26 14:51:48

动态规划为了方便，使用 ss 代指 str，使用 pp 代指 pattern。整理一下题意，对于字符串 p 而言，有三种字符：普通字符：需要和 s 中同一位置的字符完全匹配 '.'：能够匹配 s 中同一位置的任意字符 '*'：不能够单独使用 '*'，必须和前一个字符同时搭配使用，数据保证了展开全文

LifelongCode

发表于 2021-05-18 20:42:32

思路：当模式中的第二个字符不是“*”时：如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。当模式中的第二个字符是“*”时：2.1.如果字符串第一个字符跟模式第一个字展开全文

牛客786963925号

发表于 2021-07-31 17:42:52

解法一：动态规划与此题类似，此题可以采用动态规划的方法来求解。定义二维递推数组dp，其中表示字符串str的前个字符与字符串pattern的前个字符是否匹配（设dp数组行、列分别为、，其中分别为字符串str和pattern的长度）。「动态规划算法的关键是确定递推式」，对于此题有如下几种情况：（为方展开全文