【题解】剑指Offer-19 正则表达式匹配
正则表达式匹配(剑指Offer-19)
题面
请实现一个函数用来匹配包含
'.'
和'*'
的正则表达式。模式中的字符'.'
表示任意一个字符,而'*'
表示它前面的字符可以出现任意次(含0次)。在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"
与模式"a.a"
和"ab*ac*a"
匹配,但与"aa.a"
和"ab*a"
均不匹配。
示例
示例 1:
1
2
3
4
5 输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。示例 2:
1
2
3
4
5
6 输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa"
可被视为 'a' 重复了一次。示例 3:
1
2
3
4
5 输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。示例 4:
1
2
3
4
5 输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个,这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。示例 5:
1
2
3
4 输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
限制
s
可能为空,且只包含从a-z
的小写字母。p
可能为空,且只包含从a-z
的小写字母以及字符.
和*
,无连续的'*'
。
思路
DP题。详见jyd的题解
动态规划解析:
状态定义: 设动态规划矩阵 dp ,
dp[i][j]
代表字符串 s 的前 i 个字符和 p 的前 j 个字符能否匹配。转移方程: 需要注意,由于
dp[0][0]
代表的是空字符的状态, 因此dp[i][j]
对应的添加字符是s[i-1]
和p[j-1]
。
- 当
p[j-1] = '*'
时,dp[i][j]
在当以下任一情况为 true 时等于 true :
dp[i][j-2]
: 即将字符组合p[j-2] *
看作出现 0 次时,能否匹配;dp[i-1][j]
且s[i-1] = p[j-2]
: 即让字符p[j-2]
多出现 1 次时,能否匹配;dp[i-1][j]
且p[j-2] = '.'
: 即让字符'.'
多出现 1 次时,能否匹配;- 当
p[j-1] != '*'
时,dp[i][j]
在当以下任一情况为 true 时等于 true :
dp[i-1][j-1]
且s[i-1] = p[j-1]
: 即让字符p[j-1]
多出现一次时,能否匹配;dp[i-1][j-1]
且p[j-1] = '.'
: 即将字符 . 看作字符s[i-1]
时,能否匹配;初始化: 需要先初始化 dp 矩阵首行,以避免状态转移时索引越界。
dp[0][0] = true
: 代 表两个空字符串能够匹配。dp[0][j] = dp[0][j-2] 且 p[j-1] = '*'
: 首行 s 为空字符串,因此当 p 的偶数位为 * 时才能够匹配(即让 p 的奇数位出现 0 次,保持 p 是空字符串)。因此,循环遍历字符串 p ,步长为 2(即只看偶数位)。返回值: dp 矩阵右下角字符,代表字符串 s 和 p 能否匹配。
代码
1 | class Solution { |