认识达内从这里开始

题目：

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.

'*' Matches zero or more of the preceding element.

思路：'.'代表任意单字符，'*'可以代表将前面的字符去掉，也可以代表是对前面字符(包括'.')的重复（数目无限）。例子：

aa a//不匹配，很明显

aa aa //匹配

aaa aa //不匹配

aa a*//匹配，*重复a

aa .*//匹配，.代表a，*重复a

ab .*//匹配，.代表a，*重复.本身（不是.代表的a），代表b         也就是说.*可以是..  ...  .....等等，可匹配任意字符串

aab c*a*b //匹配，第一个*将c字符去掉，aab与a*b很明显匹配

public class Solution {

   public boolean isMatch(String s, String p) {

       /*

       if(p.length()==0){

           return s.length()==0;

       }

       if(p.length()==1){

           return s.length()==1&&(p.charAt(0)==s.charAt(0)||p.charAt(0)=='.');

       }

       if(p.charAt(1)=='*'){

           if(isMatch(s,p.substring(2))){

               return true;

           }

           return s.length()>0&&(p.charAt(0)==s.charAt(0)||p.charAt(0)=='.')&&isMatch(s.substring(1),p);

       }else{

           return s.length()>0&&(p.charAt(0)==s.charAt(0)||p.charAt(0)=='.')&&isMatch(s.substring(1),p.substring(1));

       }

       */

       return isMatch(s, 0, p, 0);

   }

   private boolean isMatch(String s, int i, String p, int j) {

       int ls = s.length();

       int lp = p.length();

       if (j == lp) {

           return i == ls;

       }

       // case 1: when the second char of p is ot '*'

       if ((j < lp - 1 && p.charAt(j + 1) != '*') || j == lp - 1) {

           return (i < ls && s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') && isMatch(s, i + 1, p, j + 1);

       }

       // case 2: when the second char of p is '*', complex case.

       while ((i < ls && s.charAt(i) == p.charAt(j)) || (p.charAt(j) == '.' && i < ls)) {

           if (isMatch(s, i, p, j + 2))

               return true;

           i++;

       }

       return isMatch(s, i, p, j + 2);

   }

}