面试题19：正则表达式匹配

题目：请实现一个函数用来匹配包含‘.’和‘’的正则表达式。模式中的字符‘.’表示任意一个字符，而‘’表示它前面的字符可以出现任意次（含0次）。
思路：先匹配第一个字符，如果不匹配直接返回false，如果匹配再往下，看下pattern的第二个字符是不是，待续。
解决方案：
public class Question19 {
public static boolean match(char[] str, char[] pattern){
if (str == null || pattern == null) return false;
int strIndex = 0;
int patternIndex = 0;
return matchCore(str, strIndex, pattern, patternIndex);
}
private static boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex){
// 如果匹配到尾就成功
if (strIndex == str.length && patternIndex == pattern.length) return true;
// 如果模式到尾，字符串没有到尾，匹配失败
if (strIndex != str.length && patternIndex == pattern.length) return false;
// 模式第二个字符是
if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == ''){
// 第一个位置相同，或者模式第一个位置为"."，即任意字符
if (str[strIndex] == pattern[patternIndex] && strIndex != str.length || pattern[patternIndex] == '.' && strIndex!=str.length){
// 分三种情况递归
return matchCore(str, strIndex, pattern, patternIndex+2) //视x匹配0个字符，即前一个字符出现0次
|| matchCore(str, strIndex+1, pattern, patternIndex+2) //匹配一个字符，即前一个字符仅出现1次
|| matchCore(str, strIndex+1, pattern, patternIndex); //匹配1个字符，模式保持不变
}else {
// 第一个位置不匹配，模式后移两位，也就是x*匹配0个字符
return matchCore(str, strIndex, pattern, patternIndex+2);
}

    }
    // 第一个字符匹配，但模式第二个不是*，模式和字符串都后移一位
    if (strIndex != str.length &&(str[strIndex] == pattern[patternIndex] ||pattern[patternIndex] == '.')){
        return matchCore(str, strIndex+1, pattern, patternIndex+1);
    }else {
        // 第一个字符不匹配，并且模式第二个位置不是*
        return false;
    }
}

public static void main(String[] args) {
    char[] str = new char[]{'a','a','a'};
    char[] pattern = new char[]{'a','.','a'};
    System.out.println(match(str, pattern));
}

}