二刷10. Regular Expression Matching

这道题这次算是刷透了，算是比较稳妥的解法，现场能解释清楚。

class Solution {
    /*
       s:"" a b c c e f
    p:      
    ""   T  F F
    a    F  T     |
    b    F    T   |
    c             |   
    * ------------T        
    d
        1
        
        
       s:"" a b c c e f
    p:      
    ""   T  F F
    a    F  T     |
    b    F    T   |
    d             |   
    * ------------F        
    d
    
        2
    
    match[i][j]: does p[1, i] match s[1, j] (i, j is num of chars not index)
    eg. match[3][3] here means does p = "abd" match s = "abc"
    
    
    1.s.charAt(j - 1) == p.charAt(i - 1) || p.charAt(i - 1) == '.'   
      match[i][j] = match[i - 1][j - 1]
      s == "ab"
      p == "ab"
      
    2. p.charAt(i - 1) == '*'
       2.1 p.charAt(i - 2) == s.charAt(j - 1) || p.charAt(i - 2) == '.' 
           eg. match[4][4] in 1, 
               s == "abcc",
               p == "abc*"
               match[i][j] if match[i][j - 1] || match[i - 2][j]
               meaning we can use * as multiple or zero to make a match
       2.2 eg. match[4][4] in 2, 
               s == "abcc"
               p == "abd*"
               match[i][j] = match[i - 2][j]
               can only match if we use * as zero and delete p.charAt(i - 1) and p.charAt(i - 2)
    */
    public boolean isMatch(String s, String p) {
        int sLen = s.length();
        int pLen = p.length();
        boolean[][] match = new boolean[pLen + 1][sLen + 1];
        match[0][0] = true;
        for (int i = 1; i < pLen + 1; i++){
            if (p.charAt(i - 1) == '*' && match[i - 2][0]){
                match[i][0] = true;
            }
        }
        for (int i = 1; i < pLen + 1; i++){
            for (int j = 1; j < sLen + 1; j++){
                if (p.charAt(i - 1) == s.charAt(j - 1) || p.charAt(i - 1) == '.'){
                    match[i][j] = match[i - 1][j - 1];
                } else if (p.charAt(i - 1) == '*'){
                    //* could mean zero or multiple to make a match in this scenerio
                    if (p.charAt(i - 2) == s.charAt(j - 1) || p.charAt( i - 2) == '.'){
                        match[i][j] = match[i][j - 1] || match[i - 2][j];
                    //* could mean only mean zero in this case to make a possible match
                    } else {
                        match[i][j] = match[i - 2][j];
                    }
                }
            }
        }
        return match[pLen][sLen];
    }
}