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.
这里主要是要分好类:
一、当前字符是0的情况
如果前一个字符是1,2则合法,并且num[i]= num[i-2],因为10,20不可分割
其他都是非法的return 0 即可
二、当前字符不是0的情况
这里也分为两种,当前字符可以和前面的字符合并的情况,和不能合并的情况
1、能进行合并 2[1,6],1[1,9]
2、不能进行合并 [3,9]X!=0,2[7,9],0X!=0
上代码
1 public class Solution { 2 public int numDecodings(String s) { 3 if(s==null||s.length()==0) return 0; 4 if(s.length()==1&&s.charAt(0)!='0') return 1; 5 else if(s.length()==1&&s.charAt(0)=='0') return 0; 6 //at least 2 characters 7 int [] nums = new int[s.length()]; 8 char c1 = s.charAt(0); 9 char c2 = s.charAt(1);10 if(c1=='0') return 0;11 else nums[0]=1;12 if(c2=='0'){13 if(c1=='1'||c1=='2') nums[1]=1;14 else return 0;15 }else if(c1=='2'&&(c2<='6'&&c2>='1')){16 nums[1]=2;17 } else if(c1=='1'){18 nums[1]=2;19 }else{20 nums[1]=1;21 }22 for(int i=2;i='1')){ //2[1,6]32 nums[i]=nums[i-1]+nums[i-2];33 }else if(pre=='1'){ //1[1,9]34 nums[i]=nums[i-1]+nums[i-2];35 }else if(pre>='3'&&pre<='4'){ //[3,4]X!=036 nums[i]=nums[i-1];37 }else {38 nums[i]=nums[i-1];39 }40 //上面针对当前字符不是0的情况实际上可以进行合并:总体上分为两种,当前字符可以和前面的字符合并为一个新的而数字的情况,和不能进行合并的情况41 //合并的情况是:2[1,6],1[1,9]42 //不能合并的情况是其他的情况:也就是[3,9]X!=0,2[7,9],0X!=043 }44 return nums[s.length()-1];45 }46 }