Leetcode - Regular Expression Matching

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

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

[Thoughts]:这题跟wild card有所不同， 这题*可以match的是那个*前面的char， 所以根据string的第二位是否是*去判断。
递归做法：

public class Solution {
    //对p的长度进行分类
    //p==0时， s==0 否？
    //p==1 或 p的第二个字母不是*， 
    // p的第一个字母不是.， 需要比较s，p的第一个字母是否相同, 
    // p的第二个字母是*
    public boolean isMatch(String s, String p) {
        if(p.length()==0) return s.length()==0;
        
        if(p.length()==1 || p.charAt(1) !=  '*'){//当p的第二个字母不是 * 
            if(s.length()!=0 && (p.charAt(0)==s.charAt(0) || p.charAt(0)=='.'))
                return isMatch(s.substring(1), p.substring(1));
            return false;
        }
        int i = -1;// p的第二个字母是*情况
        while(i<s.length() && (i<0 || s.charAt(i)==p.charAt(0) || p.charAt(0) == '.')){
            if(isMatch(s.substring(i+1), p.substring(2)))
                return true;
            i++;
        }
        return false;
    }
}

DP 版本， 需要足以一些细节。 尤其是初始化的那个循环。

 public boolean isMatch(String s, String p) {
       int ls = s.length(), lp = p.length();
       
       boolean[][] match = new boolean[ls+1][lp+1];
       match[0][0] = true;
       for(int i=0; i<lp-1; i++){
           if(p.charAt(i+1)!='*') break;
           match[0][i+2] = true;
           i++;
       }
       
       for(int i=0; i<ls; i++){
           for(int j=0; j<lp; j++){
               if(p.charAt(j)=='*') continue;
               boolean doc = p.charAt(j)=='.';
               boolean sta = (j<lp-1 && p.charAt(j+1) =='*') ? true : false;
               
               char cur = p.charAt(j);
               if(sta)
                match[i+1][j+2] = ((doc||cur==s.charAt(i)) && (match[i][j] || match[i][j+2])) || match[i+1][j];
               else
                match[i+1][j+1] = (doc||cur==s.charAt(i)) && match[i][j];
           }
       }
       
       return match[ls][lp];
    }