LeetCode—10.正则表达式匹配[Regular Expression Matching]——分析及代码[C++]
一、题目二、分析及代码1. 从后向前递归(1)思路(2)代码(3)结果
2. 动态规划(1)思路(2)代码(3)结果
三、其他1.长度为变量的数组
一、题目
给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。
说明: s 可能为空,且只包含从 a-z 的小写字母。 p 可能为空,且只包含从 a-z 的小写字母,以及字符 . 和 *。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。
示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个,这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/regular-expression-matching 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二、分析及代码
1. 从后向前递归
(1)思路
因为题目所给正则符号 ‘*’ 和 ‘.’ 均对前部字符起作用,因此考虑从后向前对字符串进行匹配处理; 通过递归的方法,不断缩小问题,直至解决。
(2)代码
class Solution
{
public
:
bool
isMatch(string s
, string p
) {
if (s
.size() == 0 && p
.size() == 0)
return true
;
if (p
.size() == 0)
return false
;
char tp
= p
[p
.size() - 1];
if (tp
== '*') {
if (p
[p
.size() - 2] == '.') {
p
= p
.substr(0, p
.size() - 2);
while (s
.size() > 0 && !isMatch(s
.substr(0, s
.size()), p
.substr(0, p
.size())))
s
= s
.substr(0, s
.size() - 1);
return isMatch(s
.substr(0, s
.size()), p
.substr(0, p
.size())) ? true
: false
;
}
else {
p
= p
.substr(0, p
.size() - 1);
if (s
.size() == 0 && p
.size() == 1)
return true
;
if (isMatch(s
.substr(0, s
.size()), p
.substr(0, p
.size() - 1)))
return true
;
while (s
[s
.size() - 1] == p
[p
.size() - 1] && !isMatch(s
.substr(0, s
.size() - 1), p
.substr(0, p
.size() - 1)))
s
= s
.substr(0, s
.size() - 1);
return s
[s
.size() - 1] == p
[p
.size() - 1] ? true
: false
;
}
}
else if (s
.size() == 0)
return false
;
else if (tp
== '.' || tp
== s
[s
.size() - 1])
return isMatch(s
.substr(0, s
.size() - 1), p
.substr(0, p
.size() - 1));
else
return false
;
return false
;
}
};
(3)结果
执行用时 : 32 ms, 在所有 C++ 提交中击败了 46.88% 的用户; 内存消耗 : 12.2 MB。 能够实现目标,但递归过程中多次重复的字符串复制、传入等可能消耗大量资源。
2. 动态规划
(1)思路
此题可以较容易地列出状态转移方程,通过动态规划记录子问题的求解情况,避免递归过程中大量重复操作。 状态转移方程:用 dp[i][j] 记录 s 前 i 个字符和 p 前 j 个字符的匹配情况,则
if (i
> 0 && p
[j
] == '.' || p
[j
] == s
[i
])
dp
[i
][j
] = dp
[i
][j
] || dp
[i
- 1][j
- 1];
else if (p
[j
] == '*') {
if (j
> 1)
dp
[i
][j
] = dp
[i
][j
] || dp
[i
][j
- 2];
if (i
> 0 && p
[j
- 1] == '.' || s
[i
] == p
[j
- 1])
dp
[i
][j
] = dp
[i
][j
] || dp
[i
- 1][j
];
}
注意点:从dp[0][0]开始处理,才能使初始情况被充分计算。
(2)代码
class Solution
{
public
:
bool
isMatch(string s
, string p
) {
int ssize
= s
.size(), psize
= p
.size();
bool dp
[ssize
+ 1][psize
+ 1];
for (int i
= 0; i
<= ssize
; i
++)
for (int j
= 0; j
<= psize
; j
++)
dp
[i
][j
] = false
;
s
= " " + s
;
p
= " " + p
;
dp
[0][0] = 1;
for (int i
= 0; i
<= ssize
; i
++) {
for (int j
= 1; j
<= psize
; j
++) {
if (i
> 0 && p
[j
] == '.' || p
[j
] == s
[i
])
dp
[i
][j
] = dp
[i
][j
] || dp
[i
- 1][j
- 1];
else if (p
[j
] == '*') {
if (j
> 1)
dp
[i
][j
] = dp
[i
][j
] || dp
[i
][j
- 2];
if (i
> 0 && p
[j
- 1] == '.' || s
[i
] == p
[j
- 1])
dp
[i
][j
] = dp
[i
][j
] || dp
[i
- 1][j
];
}
}
}
return dp
[ssize
][psize
];
}
};
(3)结果
执行用时 : 8 ms, 在所有 C++ 提交中击败了 89.66% 的用户; 内存消耗 : 8.4 MB。
三、其他
1.长度为变量的数组
在 C89 和 C++ 中,数组长度必须为常量,变长数组可以用 vector 表示:
vector
<vector
<bool
>>dp(ssize
+ 1, vector
<bool
>(psize
+ 1, false
));
在 C99 中,数组长度可以为变量:
bool dp
[ssize
+ 1][psize
+ 1];
在 gcc 编译器中,后者效率略高于前者(本题运行从 12ms 缩短到 8ms )。