重庆网站模版建设,张雪峰说软件工程,公司官网搭建方案,软件外包服务是什么【问题描述】[困难]
请实现一个函数用来匹配包含. 和*的正则表达式。模式中的字符.表示任意一个字符#xff0c;而*表示它前面的字符可以出现任意次#xff08;含0次#xff09;。在本题中#xff0c;匹配是指字符串的所有字符匹配整个模式。例如#xff0c;字符串…【问题描述】[困难]
请实现一个函数用来匹配包含. 和*的正则表达式。模式中的字符.表示任意一个字符而*表示它前面的字符可以出现任意次含0次。在本题中匹配是指字符串的所有字符匹配整个模式。例如字符串aaa与模式a.a和ab*ac*a匹配但与aa.a和ab*a均不匹配。示例 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
s 可能为空且只包含从 a-z 的小写字母。
p 可能为空且只包含从 a-z 的小写字母以及字符 . 和 *无连续的 *。
【解答思路】
1. 动态规划 时间复杂度O(N^2) 空间复杂度O(1)
class Solution {public boolean isMatch(String A, String B) {int n A.length();int m B.length();boolean[][] f new boolean[n 1][m 1];for (int i 0; i n; i) {for (int j 0; j m; j) {//分成空正则和非空正则两种if (j 0) {f[i][j] i 0;} else {//非空正则分为两种情况 * 和 非*if (B.charAt(j - 1) ! *) {if (i 0 (A.charAt(i - 1) B.charAt(j - 1) || B.charAt(j - 1) .)) {f[i][j] f[i - 1][j - 1];}} else {//碰到 * 了分为看和不看两种情况//不看if (j 2) {f[i][j] | f[i][j - 2];}//看if (i 1 j 2 (A.charAt(i - 1) B.charAt(j - 2) || B.charAt(j - 2) .)) {f[i][j] | f[i - 1][j];}}}}}return f[n][m];}
}
思路二
class Solution {public boolean isMatch(String s, String p) {int m s.length();int n p.length();boolean[][] f new boolean[m 1][n 1];f[0][0] true;for (int i 0; i m; i) {for (int j 1; j n; j) {if (p.charAt(j - 1) *) {f[i][j] f[i][j - 2];if (matches(s, p, i, j - 1)) {f[i][j] f[i][j] || f[i - 1][j];}}else {if (matches(s, p, i, j)) {f[i][j] f[i - 1][j - 1];}}}}return f[m][n];}public boolean matches(String s, String p, int i, int j) {if (i 0) {return false;}if (p.charAt(j - 1) .) {return true;}return s.charAt(i - 1) p.charAt(j - 1);}
}
2. 递归
时间复杂度O(N) 空间复杂度O(1)
class Solution {public boolean isMatch(String A, String B) {// 如果字符串长度为0需要检测下正则串if (A.length() 0) {// 如果正则串长度为奇数必定不匹配比如 .、ab*,必须是 a*b*这种形式*在奇数位上if (B.length() % 2 ! 0) return false;int i 1;while (i B.length()) {if (B.charAt(i) ! *) return false;i 2;}return true;}// 如果字符串长度不为0但是正则串没了return falseif (B.length() 0) return false;// c1 和 c2 分别是两个串的当前位c3是正则串当前位的后一位如果存在的话就更新一下char c1 A.charAt(0), c2 B.charAt(0), c3 a;if (B.length() 1) {c3 B.charAt(1);}// 和dp一样后一位分为是 * 和不是 * 两种情况if (c3 ! *) {// 如果该位字符一样或是正则串该位是 .,也就是能匹配任意字符就可以往后走if (c1 c2 || c2 .) {return isMatch(A.substring(1), B.substring(1));} else {// 否则不匹配return false;}} else {// 如果该位字符一样或是正则串该位是 .和dp一样有看和不看两种情况if (c1 c2 || c2 .) {return isMatch(A.substring(1), B) || isMatch(A, B.substring(2));} else {// 不一样那么正则串这两位就废了直接往后走return isMatch(A, B.substring(2));}}}
}
【总结】
1.总想着正向解决问题非但没有考虑清楚情况而且不全面没有发现子问题立即转化为递归或动态规划的思想
2.归纳整理总结 考虑清楚所有情况
3.动态规划流程
第 1 步设计状态 第 2 步状态转移方程 第 3 步考虑初始化 第 4 步考虑输出 第 5 步考虑是否可以状态压缩
转载链接https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/solution/zhu-xing-xiang-xi-jiang-jie-you-qian-ru-shen-by-je/
参考链接https://leetcode-cn.com/problems/regular-expression-matching/solution/zheng-ze-biao-da-shi-pi-pei-by-leetcode-solution/
