title: Understanding regex string matching using Dynamic Programming
body: <p>I came across this problem that asks you to implement a regular expression matcher with support for '.' and '*', where </p>
  
  <p>'.' Matches any single character.</p>
  
  <p>'*' Matches zero or more of the preceding element.</p>
  
  <pre><code>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
  </code></pre>
  
  <p>While I was able to solve this in a linear fashion, I came across lots of solutions that used DP, like the one below,</p>
  
  <pre class="lang-java prettyprint-override"><code>class Solution {
      public boolean isMatch(String text, String pattern) {
          boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];
          dp[text.length()][pattern.length()] = true;
  
          for (int i = text.length(); i &gt;= 0; i--){
              for (int j = pattern.length() - 1; j &gt;= 0; j--){
                  boolean first_match = (i &lt; text.length() &amp;&amp; 
                                         (pattern.charAt(j) == text.charAt(i) ||
                                          pattern.charAt(j) == '.'));
                  if (j + 1 &lt; pattern.length() &amp;&amp; pattern.charAt(j+1) == '*'){
                      dp[i][j] = dp[i][j+2] || first_match &amp;&amp; dp[i+1][j];
                  } else {
                      dp[i][j] = first_match &amp;&amp; dp[i+1][j+1];
                  }
              }
          }
          return dp[0][0];
      }
  }
  </code></pre>
  
  <p>I'm having a hard time understanding this. I've solved a few DP problems that involved grids (shortest path in 2d grid, largest square in binary 2d grid),  using a DP table there made perfect sense to me. However here I'm completely lost, I'm unable to understand how traversing a 2d table helps in solving this problem. Further more it appears we know when the characters don't match in the loop, so I don't understand why we don't terminate the search there (this is also probably due to my lack of understanding of how a table traversal leads to a solution). Is there a clear intuitive explanation for problems like these?</p>