邢台公司做网站,广州百度seo排名,哈尔滨发布,大理 网站建设题目描述#xff1a;
给你一个字符串 s 和一个字符规律 p#xff0c;请你来实现一个支持 . 和 * 的正则表达式匹配。
. 匹配任意单个字符* 匹配零个或多个前面的那一个元素
所谓匹配#xff0c;是要涵盖 整个 字符串 s的#xff0c;而不是部分字符串。 示例 1#xff1…
题目描述
给你一个字符串 s 和一个字符规律 p请你来实现一个支持 . 和 * 的正则表达式匹配。
. 匹配任意单个字符* 匹配零个或多个前面的那一个元素
所谓匹配是要涵盖 整个 字符串 s的而不是部分字符串。 示例 1
输入s aa, p a
输出false
解释a 无法匹配 aa 整个字符串。示例 2:
输入s aa, p a*
输出true
解释因为 * 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 a。因此字符串 aa 可被视为 a 重复了一次。示例 3
输入s ab, p .*
输出true
解释.* 表示可匹配零个或多个*任意字符.。提示
1 s.length 201 p.length 20s 只包含从 a-z 的小写字母。p 只包含从 a-z 的小写字母以及字符 . 和 *。保证每次出现字符 * 时前面都匹配到有效的字符
解法
首先理解题目的意思要判断两个字符串s和p是否匹配匹配返回true否则返回false。
.可以代表任意单个字符
*可以代表零个或多个前面的元素
一、先考虑特殊情况
1.p和s均为空串此时一定匹配。
2.p为空串s不为空串一定不匹配。
3.s为空串但p不为空串此时需要看p字符串末位是否为‘*’如果是则可以使得其左侧的字符出现零次达到消除效果如果情况正好可以消除完全则可以匹配否则不能匹配。 二、非空情况 这里是大问题包含子问题要判断s与p是否匹配那么就需要判断s与p的子串是否能匹配。
从左至右遍历s与p字符串i表示s串遍历下标j表示p串遍历下标针对每个i和j也就形成了s和p的不同子串。
我们可以s与p每个子串的末尾元素是否匹配然后判断左侧剩余子串是否匹配。
用dp[i][j]表示s的前i个字符s下标为0~i-1与p的前j个字符p下标为0~j-1是否匹配即如果dp[i][j]为trues的前i个字符与p的前j个字符匹配反之不匹配。 1.s[i-1]与p[j-1]匹配
那么如果s的第i个字符和p的第j个字符匹配的话即当s[i-1]p[j-1]字符相等或者p[j-1]..可以替代任意单个字符时两个串是否匹配则取决于除末尾位之外的剩余子串是否匹配即s的前i-1个字符与p的前j-1个字符是否匹配也就是dp[i][j]dp[i-1][j-1]。 2.s[i-1]与p[j-1]不匹配
末位不匹配分两种情况 1末位字符不等且p[j-1]不是‘*’
这种情况没办法匹配了能影响字符的只有‘.’和‘*’两个字符但是*只会影响它左侧的元素所以如果末位不等没办法通过转变来使得其匹配。
2末位字符不等但p[j-1]为‘*’
此时因为‘*’会影响左侧字符所以需要分情况考虑。
1比较p[j-2]与s[i-1]是否匹配如果匹配有以下几种情况
p[j-1]为‘*’那么p[j-2]在匹配过程中受到‘*’影响出现的次数是不确定的可能因为匹配而小时也可能出现1次、2次甚至更多次因为‘*’可以让其左侧元素出现不确定的数量只要有某一种情况可以使剩余子串匹配则可行。 2如果p[j-2]与s[i-1]不匹配
此时p[j-1]*可以使得p[j-2]出现零次而消失那么就需要比较s[i-1]和p[j-3]是否匹配。
三、整体代码
class Solution {public boolean isMatch(String s, String p) {char[] cs s.toCharArray();char[] cp p.toCharArray();// dp[i][j]s的前i个字符与p的前j个字符是否匹配boolean[][] dp new boolean[cs.length 1][cp.length 1];// s,p均为空dp[0][0] true;// p空s不空false// s空p不空分情况*影响)for (int j 1; j cp.length; j) {if (cp[j - 1] *) {dp[0][j] dp[0][j - 2];}}for (int i 1; i cs.length; i) {for (int j 1; j cp.length; j) {// 文本串和模式串末尾字符匹配if (cs[i - 1] cp[j - 1] || cp[j - 1] .) {dp[i][j] dp[i - 1][j - 1];} else if (cp[j - 1] *) {// p末尾是*// p的*的前一个字符与s末尾能匹配if (cs[i - 1] cp[j - 2] || cp[j - 2] .) {dp[i][j] dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j];} else {dp[i][j] dp[i][j - 2];}}}}return dp[cs.length][cp.length];}
} 参考题解
https://leetcode.cn/problems/regular-expression-matching/solutions/
