20_正则表达式匹配

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

方法：使用递归回溯的方法
思路： . 的匹配很简单，任何字符与 . 都能匹配，进行下一个字符匹配。
一、当模式中的第二个字符是 * 时：
  如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。
  如果字符串第一个字符跟模式第一个字符匹配，可以有3种匹配方式：
    1.模式后移2字符，相当于 x* 被忽略；
    2.字符串后移1字符，模式后移2字符，相当于 x* 匹配一位；
    3.字符串后移1字符，模式不变，即继续匹配字符下一位，相当于 x* 匹配多位；
二、当模式中的第二个字符不是 * 时：
  如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的部分。
三、如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回False。

public class L20_Match {
    public boolean match(char[] str, char[] pattern) {
        //检查边界
        if (str == null || pattern == null) {
            return false;
        }
        //定义两个指针分别指向str和pattern
        int indexOfStr = 0;
        int indexOfPattern = 0;
        return matchHelper(str, indexOfStr, pattern, indexOfPattern);
    }

    public boolean matchHelper(char[] str, int indexOfStr, char[] pattern, int indexOfPattern) {
        //判断边界条件,指针索引完成,递归退出条件
        if(indexOfStr==str.length && indexOfPattern==pattern.length){
            return true;
        }
        //indexOfPattern先到尾部则匹配失败
        if(indexOfPattern==pattern.length&&indexOfStr<str.length){
            return false;
        }
        //pattern的第二个字符为'*',且第一个字符匹配,边界为模式指针未达到末尾
        if(indexOfPattern+1<pattern.length&&pattern[indexOfPattern+1]=='*'){
            if((indexOfStr!=str.length&&str[indexOfStr]==pattern[indexOfPattern])||(indexOfStr!=str.length&&pattern[indexOfPattern]=='.')){
                return matchHelper(str,indexOfStr,pattern,indexOfPattern+2)  // *情况一：模式指针后移2字符，相当于x*被忽略，表示*前面的字符出现0次；
                        ||matchHelper(str,indexOfStr+1,pattern,indexOfPattern+2)  // *情况二：字符串后移1字符，模式后移2字符，相当于x*匹配一位,表示*前面的字符只出现1次；
                        ||matchHelper(str,indexOfStr+1,pattern,indexOfPattern);  // *情况三：匹配一个，字符串后移1字符，模式不变，即继续匹配字符下一位，相当于x*匹配多位, 表示*前面的字符出现多次；
            }else{
                //第一个字符不匹配,pattern直接移动两位
                return matchHelper(str,indexOfStr,pattern,indexOfPattern+2);
            }
        }
        //pattern的第二个字符不为'*',且第一个字符匹配
        if((indexOfStr!=str.length&&str[indexOfStr]==pattern[indexOfPattern])
                ||(indexOfStr!=str.length&&pattern[indexOfPattern]=='.')){
            return matchHelper(str,indexOfStr+1,pattern,indexOfPattern+1);
        }else{
            //第一个字符不匹配
            return false;
        }
    }
}