青岛网站建设软件下载,网站打开很慢怎么做优化,寻找电子商务网站建设,网站建设经费估算剑指 Offer#xff08;第2版#xff09;面试题 19#xff1a;正则表达式匹配 剑指 Offer#xff08;第2版#xff09;面试题 19#xff1a;正则表达式匹配解法1#xff1a;递归解法2#xff1a;动态规划 剑指 Offer#xff08;第2版#xff09;面试题 19#xff1a;… 剑指 Offer第2版面试题 19正则表达式匹配 剑指 Offer第2版面试题 19正则表达式匹配解法1递归解法2动态规划 剑指 Offer第2版面试题 19正则表达式匹配
题目来源
AcWing 30. 正则表达式匹配LeetCode 10. 正则表达式匹配
解法1递归
代码
class Solution
{
public:bool isMatch(string s, string p){if (p.empty())return s.empty();return match(s, p, 0, 0);}bool match(string s, string p, int a, int b){if (b p.size())return a s.size();else if (a s.size()){if (b p.size() - 1 || p[b 1] ! *)return false;return match(s, p, a, b 2);}if (b 1 p.size())return a 1 s.size() (s[a] p[b] || p[b] .);if (p[b 1] ! *){if (s[a] p[b] || p[b] .)return match(s, p, a 1, b 1);return false;}if (s[a] ! p[b] p[b] ! .)return match(s, p, a, b 2);return match(s, p, a, b 2) || match(s, p, a 1, b 2) || match(s, p, a 1, b);}
};注这种写法不能在 LeetCode 上通过爆栈了。 解法2动态规划
代码
class Solution
{
public:bool isMatch(string s, string p){int m s.size(), n p.size();// 状态矩阵vectorvectorbool dp(m 1, vectorbool(n 1, false));// dp[i,j]: 表示以i截止的字符串是否可以被以j截止的正则表达式匹配// 初始化dp[0][0] true;// 在匹配0次的情况下浪费一个字符星号的组合没有匹配任何s中的字符for (int i 1; i n; i)if (p[i - 1] *) //*匹配零个或多个前面的那一个元素dp[0][i] dp[0][i - 2];// 状态转移for (int i 1; i m; i)for (int j 1; j n; j){if (p[j - 1] ! *) // 当前p匹配的字符不是*{if (match(s[i - 1], p[j - 1]) true) // 当前s匹配的字符和p匹配的字符相符合dp[i][j] dp[i - 1][j - 1];else // 当前s匹配的字符和p匹配的字符不相符合dp[i,j]falsedp[i][j] false;}else // 当前p匹配的字符为*{// 当前s匹配的字符和p匹配的p中一个字符星号的组合相匹配// 要么跳过一个字符星号的组合要么看dp[i-1][j]是否为true或运算连接if (match(s[i - 1], p[j - 2]) true)dp[i][j] dp[i - 1][j] || dp[i][j - 2];else // 当前s匹配的字符和p中一个字符星号的组合不相匹配跳过该组合dp[i][j] dp[i][j - 2];}}return dp[m][n];}// 辅函数bool match(char sc, char pc){//.匹配任意单个字符故一定匹配成功if (pc .)return true;// 不然看s字符和p字符是否相同return sc pc;}
};复杂度分析
时间复杂度O(m*n)其中 m 是字符串 s 的长度n 是字符串 p 的长度。
空间复杂度O(m*n)其中 m 是字符串 s 的长度n 是字符串 p 的长度。
