Leetcode 91. Decode Ways JAVA語言

1

2

3

4

5

6

7

8

9

10

11

12

<code>A message containing letters from A-Z is being encoded to numbers using the following mapping:</code>

<code>'A' -&gt; 1</code>

<code>'B' -&gt; 2</code>

<code>...</code>

<code>'Z' -&gt; 26</code>

<code>Given an encoded message containing digits, determine the total number of ways to decode it.</code>

<code>For example,</code>

<code>Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).</code>

<code>The number of ways decoding "12" is 2.</code>

<code>Subscribe to see which companies asked this question.</code>

<code>Show Tags</code>

題意：A-&gt;1  B-&gt;2 ...Z-&gt;26;給出一個數字字元串，求可能的驿碼方式

13

14

15

16

17

18

19

20

<code>public</code> <code>class</code> <code>Solution {</code>

<code>    </code><code>public</code> <code>int</code> <code>numDecodings(String s) {</code>

<code>        </code><code>int</code> <code>length=s.length();</code>

<code>        </code><code>if</code><code>(s==</code><code>null</code> <code>|| length==</code><code>0</code><code>)</code><code>return</code> <code>0</code><code>;</code>

<code>        </code><code>int</code><code>[] dp=</code><code>new</code> <code>int</code><code>[length+</code><code>1</code><code>];</code>

<code>        </code><code>dp[</code><code>0</code><code>]=</code><code>1</code><code>;</code>

<code>        </code><code>dp[</code><code>1</code><code>]=s.charAt(</code><code>0</code><code>)==</code><code>'0'</code><code>?</code><code>0</code><code>:</code><code>1</code><code>;</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>i=</code><code>2</code><code>;i&lt;=length;i++){</code>

<code>            </code><code>int</code> <code>first=Integer.valueOf(s.substring(i-</code><code>1</code><code>,i));</code>

<code>            </code><code>int</code> <code>second=Integer.valueOf(s.substring(i-</code><code>2</code><code>,i));</code>

<code>            </code><code>if</code><code>(first&gt;</code><code>0</code><code>&amp;&amp;first&lt;</code><code>10</code><code>){</code>

<code>                </code><code>dp[i]+=dp[i-</code><code>1</code><code>];</code>

<code>            </code><code>}</code>

<code>            </code><code>if</code><code>(second&gt;=</code><code>10</code> <code>&amp;&amp; second&lt;=</code><code>26</code><code>){</code>

<code>                </code><code>dp[i]+=dp[i-</code><code>2</code><code>];</code>

<code>        </code><code>}</code>

<code>        </code><code>return</code> <code>dp[length];</code>

<code>    </code><code>}</code>

<code>}</code>

PS:看大神說可以用dp...第一次用。。其實有一小點還不明白，dp[0]=1是為什麼呢

本文轉自 努力的C 51CTO部落格，原文連結:http://blog.51cto.com/fulin0532/1902575