[Leetcode] Decode Ways

<div class="iteye-blog-content-contain" style="font-size: 14px;"> <div id="question_91" class="row-even question-title" style="margin: 0px; padding: 5px 8px; border: 1px solid #ffffff; font-size: 13px; vertical-align: baseline; cursor: pointer; color: #222222; font-family: 'Helvetica Neue', arial, sans-serif;"> <strong style="margin: 0px; padding: 0px; border: 0px; vertical-align: baseline; background-color: transparent;">Decode Ways</strong><span class="date" style="margin: 0px 10px 0px 0px; padding: 0px; border: 0px; font-size: 10px; vertical-align: baseline; background-color: transparent; color: #999999; float: right;" title="2012-06-25 21:13:00">Jun 25 '12</span><span class="stats" style="margin: 0px; padding: 1px 4px; border: 0px; font-size: 11px; vertical-align: baseline; background-color: #eeeeee; color: #999999; width: 65px; text-align: center;" title="6747 accepted submissions out of 26583 (25%)">6747 / 26583</span> </div> <div class="row-even question-content" style="margin: 0px; padding: 5px 8px 5px 55px; border: 1px solid #ffffff; font-size: 13px; vertical-align: baseline; color: #222222; font-family: 'Helvetica Neue', arial, sans-serif;"> <p style="margin-bottom: 20px; border: 0px; vertical-align: baseline; background-color: transparent;">A message containing letters from <code style="margin: 0px; padding: 1px 5px; border: 0px; font-size: 13px; vertical-align: baseline; background-color: #eeeeee; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif;">A-Z</code> is being encoded to numbers using the following mapping:</p> <pre>'A' -&gt; 1 'B' -&gt; 2 ... 'Z' -&gt; 26 </pre> <p style="margin-bottom: 20px; border: 0px; vertical-align: baseline; background-color: transparent;">Given an encoded message containing digits, determine the total number of ways to decode it.</p> <p style="margin-bottom: 20px; border: 0px; vertical-align: baseline; background-color: transparent;">For example,<br style="margin: 0px;">Given encoded message <code style="margin: 0px; padding: 1px 5px; border: 0px; font-size: 13px; vertical-align: baseline; background-color: #eeeeee; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif;">"12"</code>, it could be decoded as <code style="margin: 0px; padding: 1px 5px; border: 0px; font-size: 13px; vertical-align: baseline; background-color: #eeeeee; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif;">"AB"</code> (1 2) or <code style="margin: 0px; padding: 1px 5px; border: 0px; font-size: 13px; vertical-align: baseline; background-color: #eeeeee; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif;">"L"</code> (12).</p> <p style="margin-bottom: 20px; border: 0px; vertical-align: baseline; background-color: transparent;">The number of ways decoding <code style="margin: 0px; padding: 1px 5px; border: 0px; font-size: 13px; vertical-align: baseline; background-color: #eeeeee; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, serif;">"12"</code> is 2.</p> </div> <p> </p> <p> </p> <p>dp[i] = dp[i-1] + dp[i-2];</p> <p> </p> <p> </p> <pre name="code" class="cpp">class Solution { public: bool isValid(const string&amp; s, int a) { if (s[a] == '0') return false; else return true; } bool isValid(const string&amp; s, int a, int b) { if (s[a] &lt; '1' || s[a] &gt; '2' || (s[a] == '2' &amp;&amp; s[b] &gt; '6')) return false; else return true; } int numDecodings(string s) { int n = s.size(); if (n == 0) return 0; if (s[0] == '0') return 0; vector&lt;int&gt; dp(n, 0); dp[0] = 1; if (s[1] != '0') dp[1]++; if (isValid(s,0,1)) dp[1]++; for (int i = 2; i &lt; n; i++) { if (isValid(s, i)) dp[i] += dp[i-1]; if (isValid(s, i-1, i)) dp[i] += dp[i-2]; } return dp[n-1]; } };</pre> <p> </p> <p> </p> </div>