leetcode10

1. 递归：

 public boolean isMatch(String s, String p) {
      if(p.isEmpty())
          return s.isEmpty();
      boolean firstMatch = (!s.isEmpty()) && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
       if(p.length() >= 2 && p.charAt(1) == '*'){
               return isMatch(s,p.substring(2)) || (firstMatch&&isMatch(s.substring(1),p)  );
       }else{
           return firstMatch && isMatch(s.substring(1),p.substring(1));
       }
        
    }

2. 动态规划

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

3. 今天刷leetcode又遇到这题了

public class Solution {
    public boolean match(char[] str, char[] pattern)
    {
        return isMatch(str,0,pattern,0);
        
        
    }
    private boolean isMatch(char[] str,int i,char[] pattern,int j){
        if(j == pattern.length)
            return i == str.length;
        boolean firstMatch = (i<str.length)&&
            (str[i]==pattern[j]||pattern[j]=='.');
        if(j+1<pattern.length && pattern[j+1]=='*')
            return isMatch(str,i,pattern,j+2)||(firstMatch&&isMatch(str,i+1,pattern,j));
         else
             return firstMatch&&isMatch(str,i+1,pattern,j+1);
        
    }
}