title: regular expression matching support for '.' and '*'
body: <p><a href="http://www.leetcode.com/2011/09/regular-expression-matching.html" rel="nofollow">Implement regular expression matching with support for ‘.’ and ‘*’.</a></p>
  
  <p>‘.’ Matches any single character. ‘*’ Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).</p>
  
  <blockquote>
    <p>Some examples:</p>
    
    <p>isMatch(“aa”,”a”) → false</p>
    
    <p>isMatch(“aa”,”aa”) → true</p>
    
    <p>isMatch(“aaa”,”aa”) → false</p>
    
    <p>isMatch(“aa”, “a*”) → true</p>
    
    <p>isMatch(“aa”, “.*”) → true</p>
    
    <p>isMatch(“ab”, “.*”) → true</p>
    
    <p>isMatch(“aab”, “c*a*b”) → true</p>
  </blockquote>
  
  <p>The author gives the following solution, which is really beautiful.</p>
  
  <pre><code>bool isMatch(const char *s, const char *p) {
    assert(s &amp;&amp; p);
    if (*p == '\0') return *s == '\0';
  
    // next char is not '*': must match current character
    if (*(p+1) != '*') {
      assert(*p != '*');
      return ((*p == *s) || (*p == '.' &amp;&amp; *s != '\0')) &amp;&amp; isMatch(s+1, p+1);
    }
    // next char is '*'
    while ((*p == *s) || (*p == '.' &amp;&amp; *s != '\0')) {
      if (isMatch(s, p+2)) return true;
      s++;
    }
    return isMatch(s, p+2);
  }
  </code></pre>
  
  <p>The author also gives some further thoughts:</p>
  
  <p>If you think carefully, you can exploit some cases that the above code runs in exponential complexity. </p>
  
  <blockquote>
    <p>Could you think of some examples?  How would you make the above code
    more efficient?</p>
    
    <p>I came up one case that takes a long time to get the result while the
    length of string s and p are not huge.</p>
    
    <p>s[] = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" 
    p[] ="a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*b"</p>
  </blockquote>
  
  <p>Can anyone help me verify this answer?
  How to think this kind of finding extreme testing questions?</p>