Leetcode 10 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

Solution1: Use DP the hard part is the '*' match. If match 0, dp[i][j]=dp[i][j-2]; if match 1, dp[i][j]=dp[i][j-1]; if match 2 more, first we need s.charAt(i-1) match p.charAt(j-2) then dp[i][j]=dp[i-1][j];

 public class Solution {  
   public boolean isMatch(String s, String p) {  
     int m=s.length();  
     int n=p.length();  
     boolean[][] dp=new boolean[m+1][n+1];  
     for (int i=0; i<=m; i++) {  
       for (int j=0; j<=n; j++) {  
         if (i==0) {  
           if (j==0) dp[i][j]=true;  
           else if (p.charAt(j-1)=='*') dp[i][j]=dp[i][j-2];  
           else dp[i][j]=false;  
         }  
         else if (j==0) dp[i][j]=false;  
         else if (p.charAt(j-1)=='.') dp[i][j]=dp[i-1][j-1];  
         else if (p.charAt(j-1)=='*') {  
           dp[i][j]=dp[i][j-2] || dp[i][j-1] || (dp[i-1][j] && (p.charAt(j-2)=='.'|| p.charAt(j-2)==s.charAt(i-1)));  
         }  
         else if (p.charAt(j-1)==s.charAt(i-1)) dp[i][j]=dp[i-1][j-1];  
         else dp[i][j]=false;  
       }  
     }  
     return dp[m][n];  
   }  
 }  

Solution 2: Optimize the space from 2 dementionto 1 demention

 public class Solution {  
   public boolean isMatch(String s, String p) {  
     int m=s.length();  
     int n=p.length();  
     boolean[] dp=new boolean[n+1];  
     for (int i=0; i<=m; i++) {  
       boolean pre=false;  
       for (int j=0; j<=n; j++) {  
         boolean temp=dp[j];  
         if (i==0) {  
           if (j==0) dp[j]=true;  
           else if (p.charAt(j-1)=='*') dp[j]=dp[j-2];  
           else dp[j]=false;  
         }  
         else if (j==0) dp[j]=false;  
         else if (p.charAt(j-1)=='.') dp[j]=pre;  
         else if (p.charAt(j-1)=='*') {  
           dp[j]=dp[j-2] || dp[j-1] || (dp[j] && (p.charAt(j-2)=='.'|| p.charAt(j-2)==s.charAt(i-1)));  
         }  
         else if (p.charAt(j-1)==s.charAt(i-1)) dp[j]=pre;  
         else dp[j]=false;  
         pre=temp;  
       }  
     }  
     return dp[n];  
   }  
 }