LeetCode—10.正则表达式匹配(Regular Expression Matching)——分析及代码(C++)

mac2022-06-30  36

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; //vector<vector<bool>>dp(ssize + 1, vector<bool>(psize + 1, 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 )。

最新回复(0)