Decode Ways 512
Question
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.
Example
Given encoded message 12, it could be decoded as AB (1 2) or L (12).
The number of ways decoding 12 is 2.
Solution
num[i]代表前i个元素有多少种decode方法。
初始化:num[0]=1, num[1]=s.charAt(i-1)=='0'? 0 : 1
状态函数:
分两种情况讨论
case 1: 第i位元素单独decode(如果为'0'则不能单独decode)
num[i]=num[i-1]
case 2: 第i位元素和前一位元素一起decode(第i位元素和第i-1位元素组成的两位数必须在10~26范围内)
num[i]+=num[i-2]
代码如下:
public class Solution {
/**
* @param s a string, encoded message
* @return an integer, the number of ways decoding
*/
public int numDecodings(String s) {
// Write your code here
if(s == null || s.length() == 0){
return 0;
}
int n = s.length();
int[] num = new int[n + 1];
num[0] = 1;
num[1] = s.charAt(0) != '0' ? 1 : 0;
for(int i = 2; i <= n; i++){
if(s.charAt(i - 1) != '0'){
num[i] = num[i - 1];
}
int val = (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0';
if(val >= 10 && val <= 26){
num[i] += num[i - 2];
}
}
return num[n];
}
}