题目描述
请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配
这题对我来说至少是medium级别了，特别是第一次尝试做的时候，真是写不出来。
有个关键点就是要先处理下一个字符是星号的情况，如果遇到两个字符相同或pattern的字符是.（点号）就直接处理下一个字符的话，显然是不对的。比如 aaa，pattern是a*a，如果两个串都去掉第一个a，变成aa和*a就没法继续判断了。
public class Solution {
public boolean match(char[] str, char[] pattern)
{
return match(str,0,pattern,0);
}
public boolean match(char[] str, int i, char[] pattern, int j){
// 匹配串和模式串都到达末尾，匹配成功
if(i>=str.length&&j>=pattern.length){
return true;
}
// 匹配串未到末尾，模式串到达末尾，说明匹配失败
if (i != str.length && j >= pattern.length) {
return false;
}
//模式串未到末尾，匹配串可能到末尾也可能没到
// 下一个模式符是*
if(j+1<pattern.length&&pattern[j+1]=='*'){
// 匹配串已经结束
if (i >= str.length) {
return match(str, i, pattern, j + 2);
}
// 匹配串未结束
if(str[i]==pattern[j]||pattern[j]=='.'){
// 匹配0个
return match(str,i,pattern,j+2)||
// 匹配1个
match(str,i+1,pattern,j+2)||
// 匹配多个
match(str,i+1,pattern,j);
}else{
return match(str, i, pattern, j + 2);
}
}
// 匹配串已结束
if(i>=str.length){
return false;
}
// 匹配串未结束
else if(str[i]==pattern[j]||pattern[j]=='.'){
return match(str,i+1,pattern,j+1);
}
return false;
}
}
