《剑指offer》——正则表达式匹配
T:
前两天刚看了有关正则表达式的基本语法和用法,今天刷牛客,就恰好碰到了这个题。 根据题目的描述,最直观的一点,就是如何处理字符’.’和’*’在一起的情形,即’.*’。 不管以何种方式进行递归,总归是要从字符串和模式的最左侧开始。设置如下递归函数: isMatch(char[] str,int indexStr,char[] pattern,int indexPat){...}
该递归函数的含义为:对于从
对于带有’*’的情况,有以下3种情况: 对于前两种,在匹配时,可以有以下匹配方式: 对于第三种情况,’a’对应的’b*’,这个时候可以直接忽略’b*’,即匹配0次。 贴上代码: /** * T: 正则表达式匹配 * 请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(包含0次)。 * 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但是与"aa.a"和"ab*a"均不匹配 * * date: 2016.5.20 * @author SSS * */
public class Solution {
public boolean match(char[] str,char[] pattern) {
return this.isMatch(str,0,pattern,0);
}
/** * 递归实现 * @param str * @param indexStr * @param pattern * @param indexPat * @return */
public boolean isMatch(char[] str,int indexPat) {
// 两者都达到了最后,说明已经完全匹配
if (indexStr == str.length && indexPat == pattern.length) {
return true;
}
// 模板的index已经超出自身长度,那么就是不匹配的
if (indexPat >= pattern.length) {
return false;
}
// 考虑pattern中包含‘*’的情况
if (indexPat < pattern.length - 1 && pattern[indexPat + 1] == '*') {
if (indexStr < str.length && (str[indexStr] == pattern[indexPat] || pattern[indexPat] == '.')) {
return isMatch(str,indexStr,indexPat + 2) || isMatch(str,indexStr + 1,indexPat);
} else { // indexStr达到了末尾,但是indexPat没达到末尾,另外,对于str中的a,可能pattern中跟的是b*
return isMatch(str,indexPat + 2);
}
}
if (indexStr == str.length) {
return false;
}
if (str[indexStr] == pattern[indexPat] || pattern[indexPat] == '.') {
return isMatch(str,indexPat + 1);
}
return false;
}
// public static void main(String []args) {
// char[] str = {'a','d','b','c','d'};
// char[] pattern = {'a','.','*','*'};
// Solution1 solution1 = new Solution1();
// System.out.println(solution1.match(str,pattern));
// }
}
其中,本方法也不算是我独自想出来的,参考了讨论区里面大牛的做法,本方法算是理解之后,依葫芦画瓢得到的。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |