<p>Given an input string <code>s</code>&nbsp;and a pattern <code>p</code>, implement regular expression matching with support for <code>&#39;.&#39;</code> and <code>&#39;*&#39;</code> where:</p>

<ul>
	<li><code>&#39;.&#39;</code> Matches any single character.​​​​</li>
	<li><code>&#39;*&#39;</code> Matches zero or more of the preceding element.</li>
</ul>

<p>The matching should cover the <strong>entire</strong> input string (not partial).</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aa&quot;, p = &quot;a&quot;
<strong>Output:</strong> false
<strong>Explanation:</strong> &quot;a&quot; does not match the entire string &quot;aa&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aa&quot;, p = &quot;a*&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong> &#39;*&#39; means zero or more of the preceding element, &#39;a&#39;. Therefore, by repeating &#39;a&#39; once, it becomes &quot;aa&quot;.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;ab&quot;, p = &quot;.*&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong> &quot;.*&quot; means &quot;zero or more (*) of any character (.)&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length&nbsp;&lt;= 20</code></li>
	<li><code>1 &lt;= p.length&nbsp;&lt;= 20</code></li>
	<li><code>s</code> contains only lowercase English letters.</li>
	<li><code>p</code> contains only lowercase English letters, <code>&#39;.&#39;</code>, and&nbsp;<code>&#39;*&#39;</code>.</li>
	<li>It is guaranteed for each appearance of the character <code>&#39;*&#39;</code>, there will be a previous valid character to match.</li>
</ul>

class Solution {
public:
    
    bool isMatchHelper(string tab,string &s, string &p, int sp, int pp){
        bool retVal=false;
        
        //cout << tab << ".........." << endl;
        
        while(sp<s.size() && pp<p.size()){
              
              //cout << tab << "s=" << s.substr(sp) << endl;
              //cout << tab << "p=" << p.substr(pp) << endl;
            
              if(pp+1<p.size() && p[pp+1]=='*'){
                  
                  bool nextPart=false;
                  
                  //cout << tab << "* handler, sp=" << sp << ", pp=" << pp << endl;
                  //-------
                  while(p[pp]==s[sp] || p[pp]=='.'){

                      //cout << tab << "sp=" << sp << endl;

                      //if(pp+2 >= p.size())
                      //    break;
                      
                      if(pp+4<p.size() && p[pp]==p[pp+2] && p[pp+1]==p[pp+3])
                          break;
                      
                      if(pp+2 < p.size() && isMatchHelper(tab+"    ",s, p, sp, pp+2)){
                          nextPart=true;
                          break;
                      }
                      else{
                          sp++;
                          if(sp>=s.size())
                              break;
                      }
                  }
                  //----------
                  
                  if(!nextPart){
                      nextPart = isMatchHelper(tab+"    ", s, p, sp, pp+2);
                      //cout << tab << "after * part returned : " << (nextPart ? "true" : "false") << endl;
                  }
                  
                  //cout << tab << "*return " << (nextPart ? "true" : "false") << endl;
                  return nextPart;
              }
              
              if(s[sp]==p[pp] || p[pp]=='.'){
                  sp++;
                  pp++;
              }
              else{
                break;
              }
        }
        
        //cout << tab << "sp=" << sp << ", pp=" << pp << endl;
              
        if(sp==s.size() && pp==p.size())
            retVal=true;
        
        //special case, no momre string, is the remaining p null?
        if(sp==s.size() && pp<p.size()){
            retVal=true;
            while(pp<p.size()){
                if(p[pp+1]!='*')
                    retVal=false;
                pp+=2;
            }
        }
        
        //cout << tab << "return " << (retVal ? "true" : "false") << endl;
        return retVal;
    }
    
    bool isMatch(string s, string p) {
        int sp=0;
        int pp=0;
        return isMatchHelper("", s, p, sp, pp);
    }
};
14431