title: Time optimize C++ function to find number of decoding possibilities
body: <p>This is an <a href="https://codefights.com/interview/K2ZLJ5P6rCSAgLAu6/topics/dp-basic" rel="nofollow noreferrer">interview practice problem from CodeFights</a>. I have a solution that's working except for the fact that it takes too long to run for very large inputs.</p>
  
  <h1>Problem Description (from the link above)</h1>
  
  <p>A top secret <code>message</code> containing uppercase letters from <code>'A'</code> to <code>'Z'</code> has been encoded as numbers using the following mapping:</p>
  
  <pre><code>'A' -&gt; 1
  'B' -&gt; 2
  ...
  'Z' -&gt; 26
  </code></pre>
  
  <p>You are an FBI agent and you need to determine the total number of ways that the message can be decoded.</p>
  
  <p>Since the answer could be very large, take it modulo 10^9 + 7.</p>
  
  <h2>Example</h2>
  
  <p>For <code>message = "123"</code>, the output should be</p>
  
  <p><code>mapDecoding(message) = 3</code>.</p>
  
  <p><code>"123"</code> can be decoded as <code>"ABC"</code> <code>(1 2 3)</code>, <code>"LC"</code> <code>(12 3)</code> or <code>"AW"</code> <code>(1 23)</code>, so the total number of ways is <code>3</code>.</p>
  
  <h2>Input/Output</h2>
  
  <p><strong>[time limit] 500ms (cpp)</strong></p>
  
  <p><strong>[input] string message</strong></p>
  
  <p>A string containing only digits.</p>
  
  <p>Guaranteed constraints:</p>
  
  <p><code>0 ≤ message.length ≤ 105</code>.</p>
  
  <p><strong>[output] integer</strong></p>
  
  <p>The total number of ways to decode the given message.</p>
  
  <h1>My Solution so far</h1>
  
  <p>We have to implement the solution in a function <code>int mapDecoding(std::string message)</code>, so my entire solution is as follows:</p>
  
  <pre class="lang-cpp prettyprint-override"><code>/*0*/ void countValidPaths(int stIx, int endIx, std::string message, long *numPaths)
  /*1*/ {
  /*2*/    //check out-of-bounds error
  /*3*/    if (endIx &gt;= message.length())
  /*4*/        return;
  /*5*/    
  /*6*/    int subNum = 0, curCharNum;
  /*7*/    //convert substr to int
  /*8*/    for (int i = stIx; i &lt;= endIx; ++i)
  /*9*/    {
  /*10*/       curCharNum = message[i] - '0';
  /*11*/       subNum = subNum * 10 + curCharNum;
  /*12*/   }
  /*13*/    
  /*14*/   //check for leading 0 in two-digit number, which would not be valid
  /*15*/   if (endIx &gt; stIx &amp;&amp; subNum &lt; 10)
  /*16*/       return;
  /*17*/    
  /*18*/   //if number is valid
  /*19*/   if (subNum &lt;= 26 &amp;&amp; subNum &gt;= 1)
  /*20*/   {
  /*21*/       //we've reached the end of the string with success, therefore return a 1
  /*22*/       if (endIx == (message.length() - 1) )
  /*23*/           ++(*numPaths);
  /*24*/       //branch out into the next 1- and 2-digit combos
  /*25*/       else if (endIx == stIx)
  /*26*/       {
  /*27*/           countValidPaths(stIx, endIx + 1, message, numPaths);
  /*28*/           countValidPaths(stIx + 1, endIx + 1, message, numPaths);
  /*29*/       }
  /*30*/       //proceed to the next digit
  /*31*/       else
  /*32*/            countValidPaths(endIx + 1, endIx + 1, message, numPaths);
  /*33*/   }
  /*34*/ }    
  /*35*/
  /*36*/ int mapDecoding(std::string message) 
  /*37*/ {
  /*38*/    if (message == "")
  /*39*/        return 1;
  /*40*/    long numPaths = 0;
  /*41*/    int modByThis = static_cast&lt;int&gt;(std::pow(10.0, 9.0) + 7);
  /*42*/    countValidPaths(0, 0, message, &amp;numPaths);
  /*43*/    return static_cast&lt;int&gt; (numPaths % modByThis);
  /*44*/ }
  </code></pre>
  
  <h1>The Issue</h1>
  
  <p>I have passed 11/12 of CodeFight's initial test cases, e.g. <code>mapDecoding("123") = 3</code> and <code>mapDecoding("11115112112") = 104</code>. However, the last test case has <code>message = "1221112111122221211221221212212212111221222212122221222112122212121212221212122221211112212212211211"</code>, and my program takes too long to execute:</p>
  
  <pre><code>Expected_output:      782204094
  My_program_output:    &lt;empty due to timeout&gt;
  </code></pre>
  
  <p>I wrote <code>countValidPaths()</code> as a recursive function, and its recursive calls are on lines 27, 28 and 32. I can see how such a large input would cause the code to take so long, but I'm racking my brain trying to figure out what more efficient solutions would cover all possible combinations.</p>
  
  <p>Thus the million dollar question: <strong>what suggestions do you have to optimize my current program so that it runs in far less time?</strong></p>