Github仓库地址:https://github.com/Damaer/CodeSolution 笔记地址:https://damaer.github.io/CodeSolution/ 仓库介绍:刷题仓库:CodeSolution
请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(包含0次)。在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但是与"aa.a"和"ab*a"均不匹配
示例1输入
"aaa","a*a"
返回值
true
这道题,仔细一想,感觉情况很多,很凌乱,此处介绍的是递归的做法,其实本题还可以使用动态规划。最重要的是需要分类讨论,原串定义为str
,模式串为pattern
。
pattern
长度为0str
长度为0
,说明刚刚好匹配完,返回ture
str
长度不为0
,说明没有匹配完,返回false
pattern
的长度大于0*
和*
前面的字符去掉,相当于匹配了0
个,然后接着比较;另外一种是,如果str
的长度大于0
,并且第一个字符匹配,那就把str
的第一个字符去掉,两者接着匹配。pattern
的长度大于1
,且第2
个字符是*
,说明前面的字符可以匹配0
,1
或者多次*
,那么就直接比较第一个字符是不是匹配,同时将后面的字符进行匹配。注意:上面说的第一个字符是不是匹配,除了两个字符相等的情况,其实还有模式串的字符为'.
'的情况。
public boolean match(String str, String pattern) {
if (pattern.length() == 0) {
return str.length() == 0;
}
// 第二个字符是'*'
if (pattern.length() > 1 && pattern.charAt(1) == '*') {
// 匹配0次,直接把'*'去掉,两者判断
return match(str, pattern.substring(2))
// 第一个字符相同的时候,去掉第一个字符,判断后面的(相当于匹配多次)
|| (str.length() > 0 && firstSame(str, pattern)) && match(str.substring(1), pattern);
} else {
// 第二个字符不是 '*'的时候,判断第1个字符是否相同,相同的时候再从第2位开始比较
return str.length() > 0
&& firstSame(str, pattern)
&& (match(str.substring(1), pattern.substring(1)));
}
}
// 判断第一个字符是不是相同
private boolean firstSame(String s, String p) {
// 两个相同,或者有一个是"."
return s.charAt(0) == p.charAt(0) || p.charAt(0) == '.';
}
当然,这种做法不是最优的,使用了大量的递归操作,并且重复递归,时间复杂度比较高。
【作者简介】:
秦怀,公众号【秦怀杂货店】作者,技术之路不在一时,山高水长,纵使缓慢,驰而不息。个人写作方向:Java源码解析,JDBC,Mybatis,Spring,redis,分布式,剑指Offer,LeetCode等,认真写好每一篇文章,不喜欢标题党,不喜欢花里胡哨,大多写系列文章,不能保证我写的都完全正确,但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处,还望指正。
平日时间宝贵,只能使用晚上以及周末时间学习写作 - END -