10. Regular Expression Matching

recursion

T: O(|s| * |p|), |s| is s state, |p| is p state,

S: O(|s| * |p|),

class Solution {
    public boolean isMatch(String s, String p) {
        if (p.isEmpty()) { // terminal
            return s.isEmpty();
        }
        boolean firstMatch = (!s.isEmpty()) && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
        
        
        // Then, we may ignore this part of the pattern, or delete a matching character in the text.
        if (p.length() >= 2 && p.charAt(1) == '*') {
						// 1. x* matches empty string or at least one character: x* -> xx*
            // 2. *s is to ensure s is non-empty
            // 1. 当p的第二个字符为*号时，由于*号前面的字符的个数可以任意，可以为0，那么我们先用递归来调用为0的情况，就是直接把这两个字符去掉再比较
            // 2. 或者当s不为空，且第一个字符和p的第一个字符相同时，再对去掉首字符的s和p调用递归，注意p不能去掉首字符，因为*号前面的字符可以有无限个
            return (isMatch(s, p.substring(2))) || 
                (firstMatch && isMatch(s.substring(1), p));
        } else {
            // 如果第二个字符不为*号，那么就老老实实的比较第一个字符，然后对后面的字符串调用递归
            return firstMatch && isMatch(s.substring(1), p.substring(1));
        }
        
    }
}

/*
key is '*' Matches zero or more of the preceding element.

   "ab", "a.*b"
       |
   (a,a)     &     (b , .*b)
              /                 \ 
    .* matches 0             .* matches > 0 chars
      |                          |
      (b,b) return true first
 */

dp

1. 
dp[i][j]: The matching pattern p[0:j] should cover the entire input string s[0:i].

2. think of these conditions
dp[i-1][j-1]
dp[i][j-1]
dp[i-1][j]


if (isChar(p[j])) {
    dp[i][j] = s[i] == p[j] && dp[i-1][j-1]
}
if (p[j] == '.') {
    dp[i][j] = dp[i-1][j-1]
}

possible1
xxxxxz
yyyyz*

possible2
xxxxxx
yyyyz*  => z* is empty
if (p[j] == '*') {
    possible1 = (p[j-1] == s[i] || p[j-1] == '.') && dp[i-1][j])  // when * means not empty
    possible2 = dp[i][j-2])  // when * means empty, 
    dp[i][j] = possible1 || possible2;
}

3. think of these init value
dp[0][0] = true
dp[0][j] =  (p[j] == *) && dp[0][j-2]
input = ""
so only in p = y*y*y* && y* = ""  can be done, so dp[0][j] = (p[j] == *) && dp[0][j-2]


dp[i][0]
pattern = ""; so all false


time: O(m*n)
space: O(m*n)

time: O(mn)

space: O(mn)

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];
        
        s = "#" + s;
        p = "#" + p;
        
        dp[0][0] = true;
        for (int j = 2; j <= n; j++) {
            dp[0][j] =  (p.charAt(j) == '*') && dp[0][j-2];
        }
        
        for (int i = 1 ; i <= m; i++) {
            for (int j = 1; j <= n; j++) {

                if ((s.charAt(i) == p.charAt(j)) || p.charAt(j) == '.') {
                    dp[i][j] = dp[i-1][j-1];
                }
                
                if (p.charAt(j) == '*') {
                    // when * means not empty
                    boolean possible1 = (p.charAt(j-1) == s.charAt(i) || p.charAt(j-1) == '.') && dp[i-1][j]; 
                        
                    // when * means empty, 
                    boolean possible2 = dp[i][j-2];
                    
                    dp[i][j] = possible1 || possible2;
                }
            }
        }
        return dp[m][n];
    }
}