LeetCode 91 Decode Ways
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1'B' -> 2...'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,Given encoded message "12", it could be decoded as "AB"
(1 2) or "L" (12). The number of ways decoding "12" is 2.
又是一道可以回溯或是dp的題目目木，一開(kāi)始按照回溯的思路，每次判斷當(dāng)前index的個(gè)位數(shù)與index,index+1對(duì)應(yīng)的兩位數(shù)，查看兩種情況是否滿足decode要求，即個(gè)位數(shù)在1-9之間，兩位數(shù)在1-26之間腊状。寫(xiě)完了以后LTE了。。姑宽。
寫(xiě)了1個(gè)半小時(shí)才改對(duì)dp的版本。闺阱。炮车。真是無(wú)語(yǔ)了。酣溃。瘦穆。
注意初始條件：
- 當(dāng)長(zhǎng)度小于什么時(shí)，應(yīng)該直接返回赊豌？
- 應(yīng)該初始化dp[0]和dp[1]嗎扛或？分別初始化成什么？
- 寫(xiě)出遞推公式
這里有一個(gè)誤區(qū)碘饼，真正的判斷條件應(yīng)該是：
個(gè)位數(shù)在1-9之間熙兔，兩位數(shù)在10-26之間！Ｅ擅痢黔姜！
代碼：
public class Solution {
public int numDecodings(String s) {
int n = s.length();
if (n <= 0) return 0;
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = (s.charAt(0) == '0') ? 0 : 1;
for (int i = 2; i <= n; i++) {
int first = Integer.valueOf(s.substring(i-1,i));
int second = Integer.valueOf(s.substring(i-2,i));
if (first >= 1 && first <= 9)
dp[i] += dp[i-1];
if (second >= 10 && second <= 26)
dp[i] += dp[i-2];
}
return dp[n];
}
}
