Question

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

思路：递归。使用两个指针记录两个字符串的匹配位置。

若pattern下一个字符有' * '，如果该字符匹配或者此位置为' . '，str指针向右移动1位（表示该字符可能出现多于一次），或者pattern指针向右移动两位（表示该字符出现0次）； 如果字符不匹配，那么该字符肯定出现0次，pattern指针向右移动两位。

若pattern下一个字符没有' * '， 也是分为上面两种情况。

public class Solution {
  public boolean match(char[] str, char[] pattern)
  {
    return match(str, 0, pattern, 0);
  }
  private boolean match(char[] str, int strIndex, char[] pattern, int patternIndex){
    //两个字符串同时检查完
    if(strIndex == str.length && patternIndex == pattern.length){
      return true;
    //pattren先检查完
    }else if(patternIndex == pattern.length){
      return false;
    }
    //判断pattern下一个字符有'*'，从而分为两种情况
    boolean flag = (patternIndex < pattern.length - 1) && (pattern[patternIndex+1] == '*');
    if(flag){
      //如果该字符匹配或者此位置为'.'
      //注意是在这里判断strIndex是否越界，因为str为空时可以与".*"匹配
      if(strIndex < str.length && (pattern[patternIndex] == '.' || str[strIndex] == pattern[patternIndex])){
        //分两种情况，前者表示'*'前的字符可能出现多于一次，后者表示该字符出现0次。
        return match(str, strIndex+1, pattern, patternIndex) || match(str, strIndex, pattern, patternIndex+2);
      }else{//该字符不匹配
        //这时只有一种可能，那就是'*'前的字符出现0次。
        return match(str, strIndex, pattern, patternIndex+2);
      }
    }else{//同样分上面两种情况
      if(strIndex < str.length && (pattern[patternIndex] == '.' || str[strIndex] == pattern[patternIndex])){
        //此时，对应字符相匹配，那么检查下一个字符是否匹配
        return match(str, strIndex+1, pattern, patternIndex+1);
      }else{
        //该字符不匹配则整个字符串不匹配
        return false;
      }
    }
  }
}