【LeetCode-010】Regular Expression Matching
【LeetCode-010】Regular Expression Matching
1题目
Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.The matching should cover the entire input string (not partial).
Note:
scould be empty and contains only lowercase lettersa-z.pcould be empty and contains only lowercase lettersa-z, and characters like.or*.
Example 1:
Input:s = "aa"
p = "a"Output: falseExplanation: "a" does not match the entire string "aa".Example 2:
Input:s = "aa"
p = "a*"Output: trueExplanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".Example 3:
Input:s = "ab"
p = ".*"Output: trueExplanation: ".*" means "zero or more (*) of any character (.)".Example 4:
Input:s = "aab"
p = "c*a*b"Output: trueExplanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".Example 5:
Input:s = "mississippi"
p = "mis*is*p*."Output: false2翻译
给定一个字符串 (s) 和一个字符模式 (p)。实现支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。匹配应该覆盖整个字符串 (s) ，而不是部分字符串。
说明:
s可能为空，且只包含从a-z的小写字母。p可能为空，且只包含从a-z的小写字母，以及字符.和*。
3分析
'.' 代表一个任意字符，与其附近的字符无关
'*' 代表o个或者多个前面的字符，该字符影响前面字符的“存在”，例如：a*={ε，a，aa，aaa，…}，即当"*"表示0个前面的字符时，该字符串为空串ε。
题目要求匹配整个输入字符串，即完全匹配，分如下情况：
同时为空则true
p为ε时，s为ε则匹配
s为ε时，p为ε则匹配，但此时p分两种情况：
1、p确实为ε
2、p为”a*“类型，此时*代表前面的字符存在0次，则p在匹配意义上位ε
不同时为空就需要比较
p字符串中当前字符是否匹配与其下一个是否为’*‘有关，所以分两种情况
[p+1]=='*' 则 匹配当前字符或者匹配下两个字符[p+2]（即不匹配当前字符，此时*表示当前字符出现零次，即p=ε[p+2]）
[p+1]!='*' 对当前字符进行匹配
3解法
思路一
public boolean isMatch(String s, String p) {
//1、字符同时为空的情况
//1.1先考虑p为空，此时只要看s是否为空即可。
if(p.length()==0) return s.length()==0;
//1.2 再考虑s为空的情况
else if(s.length()==0)
{
//1.2.1 p分两种情况
//if(p.length()==0)return true;//情况1 p确实为空。
if(p.length()>1&&p.charAt(1)=='*')return isMatch(s,p.substring(2));//情况二，”匹配“意义上为空
else return false;
}
//2、不同时为空则进行匹配
else
{
//2.1 如果p的下一个字符为’*‘则分两种情况
if(p.length()>1&&p.charAt(1)=='*')
{
//2.1.1 匹配下两个字符
if(isMatch(s,p.substring(2))) return true;
//2.1.2 匹配当前字符，注意：此时p字符串不步进
else if(s.charAt(0)==p.charAt(0)||p.charAt(0)=='.')return isMatch(s.substring(1),p);
else return false;
}
//2.2 匹配当前字符
else
{
if(s.charAt(0)==p.charAt(0)||p.charAt(0)=='.')return isMatch(s.substring(1),p.substring(1));
else return false;
}
}
}
思路二
大佬级别的解法，来自官网，执行时间是上边思路一解法的1/6，惭愧惭愧，如下贴出来提供大家欣赏学习
public boolean isMatch(String text, String pattern) {
boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];
dp[text.length()][pattern.length()] = true;
for (int i = text.length(); i >= 0; i--){
for (int j = pattern.length() - 1; j >= 0; j--){
boolean first_match = (i < text.length() &&
(pattern.charAt(j) == text.charAt(i) ||
pattern.charAt(j) == '.'));
if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
} else {
dp[i][j] = first_match && dp[i+1][j+1];
}
}
}
return dp[0][0];
}4总结
总体而言，今天这道题有点难，刚开始想着直接去迭代，然后逐一排除各种情况，最后虽然几经调试成功了，但是执行时间也是很不理想，超过了666ms，没超时已经算是谢天谢地了。
所以写代码之前最好还是想清楚要怎么写，不要提起键盘就是干，到头来，都不知道自己写的是啥玩意！