[leetcode]Decode Ways

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.

算法思路：

思路1：递归。典型的递归算法，不用试就知道会超时。

思路2：dp。既然递归超时，那就不妨试试dp了。

维护一个一维数组，dp[length]。dp[i]表示字符串 i ~ length的decode ways。

初始状态：dp[length] = 0; dp[length - 1] = dp[length - 1] = s.charAt(length - 1) == '0' ? 0 : 1;

每次读取num = s.substring(i,i + 2)

如果大于26，则dp[i] = dp[i + 1];

如果小于等于26，则dp[i] = dp[i + 1] + dp[i + 2];

【注意】0的处理，第一遍未通过case“0”，"01"，"101"

 1 public class Solution {
 2     public int numDecodings(String s) {
 3         if(s.length() == 0) return 0;
 4         int length = s.length();
 5         int[] dp = new int[length + 1];
 6         dp[length] = 1;
 7         dp[length - 1] = s.charAt(length - 1) == '0' ? 0 : 1; 
 8         for(int i = length - 2; i >= 0; i--){
 9             if(s.charAt(i) == '0') continue;
10             int tem = Integer.valueOf(s.substring(i,i + 2));
11             if(tem > 26){
12                 dp[i] = dp[i + 1];
13             }else{
14                 dp[i] = dp[i + 1] + dp[i + 2];
15             }
16         }
17         return dp[0];
18     }
19 }