首页 > 代码库 > LeetCode OJ - Decode ways
LeetCode OJ - Decode ways
这道题用动规啊!!
但是呢,有很多细节需要注意的啊!!特别是当0出现的时候。下面就来详细讲下啦!
首先设一个长度为len+1的数组num,num[i]表示s[0...i-1]的解码方式。然后我们假设i之前的num都计算好了,现在来计算num[i],考虑s[i-1],s[i-1]一般来说有两种解码方式,一是单独s[i-1]进行解码;二是把s[i-2]和s[i-1]作为一个码进行解析,如果情况允许的话。因此有如下递推公式:
num[i] = num[i-1] + num[i-2]; ( s[i-2] = ‘1‘ || (s[i-2] =‘2‘ && ‘0‘<=s[i-1]<=‘6‘)) && ((i<len && s[i] !=0)||i=len )
num[i-1]; otherwise
0; s[0] = ‘0‘ ; s[i-2] = ‘0‘ and s[i-1] = ‘0‘ ; s[i-1] <‘0‘ and s[i-1]>‘9‘ 当出现0的时候可以直接return
1 ; i = 1时
下面是AC代码:
1 /** 2 * A message containing letters from A-Z is being encoded to numbers using the following mapping: 3 * ‘A‘ -> 1 4 * ‘B‘ -> 2 5 * ... 6 * ‘Z‘ -> 26 7 * Given an encoded message containing digits, determine the total number of ways to decode it. 8 * @param s 9 * @return 10 */ 11 public int numDecodings(String s){ 12 if(s == null || s.length() == 0) 13 return 0; 14 if(s.length() == 1 && s.charAt(0)-‘0‘>0 && s.charAt(0)-‘0‘ <=9) 15 return 1; 16 else if(s.length() == 1) 17 return 0; 18 19 int len = s.length(); 20 int [] num = new int[len+1]; 21 num[0] = 1; 22 num[1] = 1; 23 if(s.charAt(0) == ‘0‘) 24 return 0; 25 for(int i=2;i<=len;i++){ 26 char last = s.charAt(i-2); 27 char cur = s.charAt(i-1); 28 if(cur == ‘0‘){ 29 if(last == ‘1‘ || last == ‘2‘) 30 { 31 num[i] = num[i-1]; 32 continue; 33 }else{ 34 return 0; 35 } 36 } 37 38 if(cur-‘0‘>0 && cur-‘0‘<=9){ 39 if((last == ‘1‘ || (last == ‘2‘ && cur-‘0‘ <=6)) && (i<len && s.charAt(i)!=‘0‘ || i == len)) 40 num[i] = num[i-1] + num[i-2]; 41 else 42 num[i] = num[i-1]; 43 }else 44 return 0; 45 46 } 47 return num[len]; 48 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。