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.
Analysis:
This is a DP problem. d[i] is the number of ways to decode the first i chars.
d[i]=d[i-2]+d[i-1] if num(i-1,i) is a valid number and num(i,i) is a valid number.
NOTE: for a string with 2 chars, the number should be between 10 and 26. For a string with 1 char, the valid number should between 1 and 9. "0","01","02"...like this are all invalid.
Solution:
1 public class Solution {
2 public int numDecodings(String s) {
3 if (s.length()==0) return 0;
4 int[] d = new int[s.length()+1];
5 d[0]=1;
6 for (int i=1;i<d.length;i++){
7 d[i]=0;
8 int start = 0;
9 if (i-2>start) start = i-2;
10 for (int k=start;k<i;k++){
11 String temp = s.substring(k,i);
12 if (temp.length()==1&&!temp.equals("0"))
13 d[i]+=d[k];
14 if (temp.length()==2){
15 int num = Integer.parseInt(temp);
16 if (num<=26 && num>=10)
17 d[i]+=d[k];
18 }
19 }
20 }
21 return d[s.length()];
22 }
23 } 轉載于:https://www.cnblogs.com/lishiblog/p/4098786.html