LeetCode第十题-正则表达式匹配

时间:2022-10-27 14:10:58

Regular Expression Matching

问题简介:给定字符串,给定匹配模式,判断字符串是否满足匹配模式

问题详解:一共有两种特殊模式:

‘.’ 匹配任何单个字符

‘*’ 匹配前面元素的零个或多个

注:匹配的是整个给定字符串,不是部分

举例:

1:

输入:

s = “aa”

p = “a”

输出: false

解释: “a” 不匹配 “aa”.

2:

输入:

s = “aa”

p = “a*”

输出: true

解释: ‘*’ 代表 0 或多个字符 ‘a’

3:

输入:

s = “ab”

p = “."

输出: true

解释: ".” 代表 0 或多个任意字符

4:

输入:

s = “aab”

p = “cab”

输出: true

5:

输入:

s = “mississippi”

p = “misisp*.”

输出: false

解法一:递归

先判断输入模式,当模式为空时,只判断输入文本是否为空即可

将输入文本与模式逐字符匹配,当碰到特殊符号’.‘时相当于匹配任何字符,碰到’*'时则改变字符串进入递归下一次判断

LeetCode第十题-正则表达式匹配

解法二:Dynamic Programming

进行解法一的递归,我们采取缓存中间结果来节省建立字符串的空间

LeetCode第十题-正则表达式匹配

小白刷题之路,请多指教— — 要么大器晚成,要么石沉大海

LeetCode第十题-正则表达式匹配