mirror of
https://gitee.com/coder-xiaomo/leetcode-problemset
synced 2025-01-10 18:48:13 +08:00
69 lines
2.7 KiB
HTML
69 lines
2.7 KiB
HTML
<p>You have intercepted a secret message encoded as a string of numbers. The message is <strong>decoded</strong> via the following mapping:</p>
|
|
|
|
<p><code>"1" -> 'A'<br />
|
|
"2" -> 'B'<br />
|
|
...<br />
|
|
"25" -> 'Y'<br />
|
|
"26" -> 'Z'</code></p>
|
|
|
|
<p>However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes (<code>"2"</code> and <code>"5"</code> vs <code>"25"</code>).</p>
|
|
|
|
<p>For example, <code>"11106"</code> can be decoded into:</p>
|
|
|
|
<ul>
|
|
<li><code>"AAJF"</code> with the grouping <code>(1, 1, 10, 6)</code></li>
|
|
<li><code>"KJF"</code> with the grouping <code>(11, 10, 6)</code></li>
|
|
<li>The grouping <code>(1, 11, 06)</code> is invalid because <code>"06"</code> is not a valid code (only <code>"6"</code> is valid).</li>
|
|
</ul>
|
|
|
|
<p>Note: there may be strings that are impossible to decode.<br />
|
|
<br />
|
|
Given a string s containing only digits, return the <strong>number of ways</strong> to <strong>decode</strong> it. If the entire string cannot be decoded in any valid way, return <code>0</code>.</p>
|
|
|
|
<p>The test cases are generated so that the answer fits in a <strong>32-bit</strong> integer.</p>
|
|
|
|
<p> </p>
|
|
<p><strong class="example">Example 1:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">s = "12"</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">2</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<p>"12" could be decoded as "AB" (1 2) or "L" (12).</p>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 2:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">s = "226"</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">3</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<p>"226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).</p>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 3:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">s = "06"</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">0</span></p>
|
|
|
|
<p><strong>Explanation:</strong></p>
|
|
|
|
<p>"06" cannot be mapped to "F" because of the leading zero ("6" is different from "06"). In this case, the string is not a valid encoding, so return 0.</p>
|
|
</div>
|
|
|
|
<p> </p>
|
|
<p><strong>Constraints:</strong></p>
|
|
|
|
<ul>
|
|
<li><code>1 <= s.length <= 100</code></li>
|
|
<li><code>s</code> contains only digits and may contain leading zero(s).</li>
|
|
</ul>
|