题目描述
请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
时间限制：1秒 空间限制：32768K
解题思路
1、先判断模式串是否为空、再判断字符串是否为空。i表示字符串str的当前索引、j表示模式串pattern的当前索引
1、若剩余模式串pattern为空，则看剩余字符串str是否为空，同时为空返回true，否则返回false
2、若剩余模式串pattern不为空，先判断剩余字符串str是否为空
（1）剩余字符串str为空，则只有'a*'这种模式串能匹配(a为任意字符，也可以为'.')
（2）剩余字符串str不为空，那么判断剩余模式串是哪种形式
——1）若剩余模式串为1位或者不小于2位并且第2位不为'*'(可能是字母也可能是'.')
——2）若剩余模式串不小于2位并且第2位为'*'，则判断第1位是否匹配
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)
{
//1、若剩余的模式串为空，则看剩余字符串是否为空，同时为空返回true，否则返回false
if(pattern.length==j) return str.length==i?true:false;
//2、剩余模式串不为空，先判断剩余字符串是否为空
//(1)剩余字符串为空，则只有'a*'这种模式串能匹配(a为任意字符，也可以为'.')
if(str.length==i) return pattern.length==2+j&&pattern[j+1]=='*'?true:false;
//(2)剩余字符串不为空，那么判断剩余模式串是哪种形式
// 1)若剩余模式串为1位或者不小于2位并且第2位不为'*'(可能是字母也可能是'.')
if((pattern.length>j+1&&pattern[j+1]!='*')||pattern.length==j+1){
//此时剩余字符串已经确定不为空，因此字符串和模式串符合条件时其索引同时右移一位
return str[i]==pattern[j]||pattern[j]=='.'?match(str,i+1,pattern,j+1):false;
}
else//2)若剩余模式串不小于2位并且第2位为'*',此时剩余字符串不为空
{
//若剩余模式串第1位能和剩余字符串第1位匹配，则剩余字符串右移1位继续匹配(匹配1+次)或模式串右移2位(匹配0次)
if(str[i]==pattern[j]||pattern[j]=='.') return match(str,i+1,pattern,j)||match(str,i,pattern,j+2);
else return match(str,i,pattern,j+2);//第1位不匹配，则模式串匹配0次
}
}
}
