string_dp.cpp

/*
This file contains the core code for dynamic programming
related to string
*/

/* LC 10. Regular expression matching 
dp (i,j): can first i char of s match first j char of p
case 1. p[j-1] != '*' and p[j-1] != '.' ==> function: dp[i-1][j-1] && s[i-1] == p[j-1]
case 2. p[j-1] == '.' ==> dp[i-1][j-1]
case 3. p[j-1] == '*' 
3.a.p[j-2] != '.' and s[i-1] != p[j-2], (make p[j-2] disappear) ==> function: dp[i][j-2]
3.b. p[j-2] == '.': dp[i][j-2] (repeat 0 time) || dp[i][j-1] (repeat 1 time) || 
dp[i-1][j] (repeat two or more)
*/
bool isMatch(string s, string p){
  // initialize 
  
  // base case
  
  // core code
  for (int i = 1; i <= s.length(); ++i){
    for (int j = 1; j <= p.length(); ++j){
      if (p[j-1] == '.') {
        dp[i][j] = dp[i-1][j-1];
      } else if (p[j-1] != '*'){
        dp[i][j] = dp[i-1][j-1] && s[i-1] == p[j-1];
      } else if (p[j-2] != '.' && s[i-1] != p[j-2]){
        dp[i][j] = dp[i][j-2];
      } else {
        dp[i][j] = dp[i][j-2] || dp[i][j-1] || dp[i-1][j];
      }
    }
  }
  return false;
}