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.
一刷
题解：
爬楼梯climb stairs，典型的一维DP。下面就用一维DP来做。先建立数组dp = new int[s.length() + 1]， 初始化一个数字的情况dp[0] = 1， 两个数字组成一个两位数字的情况dp[1] = 1。接下来写出循环体，先算一个数字的情况，当s.charAt(i - 1)不为0的时候，dp[i] = dp[i - 1]， 否则dp[i] = 0。 接下来考虑两位数字，当由i-2和i-1这两位组成的数字大于等于10，小于等于26时，dp[i] += dp[i - 2]， 否则忽略此种情况。
Time Complexity - O(n)， Space Complexity - O(n)
public class Solution {
public int numDecodings(String s) {
if(s == null || s.isEmpty() || s.charAt(0) == '0') return 0;
int len = s.length();
int[] numWays = new int[len+1];
numWays[0] = 1;//empty String
numWays[1] = 1; //one char
for(int i=2; i<=len; i++){
int num = Integer.parseInt(s.substring(i-2, i));
numWays[i] = (num <=26 && num>=10)? numWays[i-2]:0;
numWays[i] += (s.charAt(i-1)!='0')? numWays[i-1]:0;
}
return numWays[len];
}
}
如果用两个int存储dp[i-2] 和 dp[i - 1], 则可以将Space Complexity降为O(1)
