正则表达式匹配

题目

请实现一个函数用来匹配包括’.’和’*’的正则表达式。模式中的字符’.’表示任意一个字符，而’*’表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”ab*ac*a”匹配，但是与”aa.a”和”ab*a”均不匹配

解题

字符相等，sId+1,pId+1
遇到点，sId+1,pId+1
遇到星号
表示它前面的字符可以出现任意次（包含0次）
//1、模式串当前字符出现0次，即*表示当前字符出现0次，则str=str,pattern=pattern+2;
//2、模式串当前字符出现1次，即*表示当前字符出现1次，则str=str+1,pattern=pattern+2;
//3、模式串当前字符出现2次或2次以上，即*表示当前字符出现2次或以上，则str=str+1,pattern=pattern;

直接讨论中复制的程序

public class Solution {
   public boolean match(char[] str,char[] pattern){
        if(str==null||pattern==null)
            return false;
        return isMatch(str,0,pattern,0);
    }
    ///三种可能：
    //1、模式串当前字符出现0次，即*表示当前字符出现0次，则str=str,pattern=pattern+2;
    //2、模式串当前字符出现1次，即*表示当前字符出现1次，则str=str+1,pattern=pattern+2;
    //3、模式串当前字符出现2次或2次以上，即*表示当前字符出现2次或以上，则str=str+1,pattern=pattern;
    public boolean isMatch(char[] str,int sIndex,char[] pattern,int pIndex){
        if(sIndex==str.length&&pIndex==pattern.length)
            return true;
        if(sIndex!=str.length&&pIndex==pattern.length)
            return false;
        //排除特例：a和a*a 
        //由于后面还有一个a所以前面a*需要当作 "0",就算str[]和pattern[]相等,也得舍去，看作不相同
        //所以isMatch(str,sIndex,pIndex+2)这句也需要加上
        if(pIndex+1<pattern.length&&pattern[pIndex+1]=='*'){
            if(sIndex<str.length&&(str[sIndex]==pattern[pIndex]||pattern[pIndex]=='.'))
                return isMatch(str,pIndex+2)|| // 匹配0 个
                isMatch(str,sIndex+1,pIndex+2)|| // 匹配 1 个
                isMatch(str,pIndex); // 匹配多个，pIndex不变可以继续匹配
            else{
                return isMatch(str,pIndex+2);// 匹配0 个
            }

        }
        if(sIndex<str.length&&(str[sIndex]==pattern[pIndex]||pattern[pIndex]=='.'))
            return isMatch(str,pIndex+1);
        return false;

    }
}