目录
题目
解题思路
代码
题目
一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1 'B' -> 2 ... 'Z' -> 26 给定一个只包含数字的非空字符串，请计算解码方法的总数。
示例 1:
输入: "12" 输出: 2 解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。 示例 2:
输入: "226" 输出: 3 解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/decode-ways 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
动态规划，dp
代码
/**
* 字母解码数字方法
*
*/
public class NumberDecodingSolution {
public static void main(String[] args) {
String s = "1110";
System.out.println(numberDecodings(s));
}
public static int numberDecodings(String s){
int len = s.length();
if (len == 0 || s.charAt(0) == '0') return 0;
// res[i] 表示第i位结束的字符串有的解码方式总数
int res[] = new int[len];
res[0] = 1;
// dp
for (int i = 1; i < len; i++) {
int current = Integer.valueOf(String.valueOf(s.charAt(i-1))) * 10 + Integer.valueOf(String.valueOf(s.charAt(i)));
int currentLocation = Integer.valueOf(String.valueOf(s.charAt(i)));
// 0
if (currentLocation == 0){
// 只能和前面的一起翻译
if(i >= 2 && (current / 10 == 1 || current / 10 == 2 )){
// 能和前面的一起翻译
res[i] = res[i-2];
}else if(i == 1 && (current / 10 == 1 || current / 10 == 2 )){
// 能和前面的一起翻译
res[i] = res[i-1];
}else {
// 不能和前面一起翻译
res[i] = 0;
}
}else{
// 不为0
if (current <= 26 && current >= 11){
// 和前一位组成的数字属于[11,26],能单独翻译也能和前一位一起翻译,res = 单独翻译 + 一起翻译
int temp = i == 1?1:res[i-2];
res[i] = res[i-1] + temp;
}else if(current <= 9 && current >= 1){
// 属于[1,9],只能单独翻译
res[i] = res[i-1];
}else if(current >= 27){
// 属于[27,...]，
res[i] = res[i-1];
}
}
}
return res[len-1];
}
}
