解码方法
程序员文章站
2022-03-05 09:57:14
...
题目:解码方法
题目描述:
一条包含字母 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) 。
public class NumDecoding {
public static void main(String[] args) {
// TODO Auto-generated method stub
String s = "102";
System.out.println(numDecoding(s));
}
public static int numDecoding(String s) {
// 字符串为空或者长度为0
/*
* if (s == null || s.length() == 0) { return 0; } //构建一个一维数组,将字符串放入到里面 int[] dp
* = new int[s.length() + 1];
*
* dp[0] = 1; dp[1] = s.charAt(0) != '0' ? 1 : 0;
*
* for (int i = 2; i <= s.length(); i++) { if(s.charAt(i-1) != '0') { dp[i] =
* dp[i-1]; } int twoNumber = (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) -
* '0'; if (twoNumber >= 10 && twoNumber <= 26) { dp[i] += dp[i - 2] ; } }
* return dp[s.length()] ;
*/
int num = s.length();
int[] dp = new int[num];
//第一个字符的情况
if (num == 0 || s.charAt(0) == '0') {
return 0;
} else {
dp[0] = 1;
}
if (s.length() == 1)
return dp[0];
//第二个字符的情况
if (s.charAt(1) != '0')
dp[1] = 1;
//第一个字符和第二个字符组成的数字大于等于10或者小于等于26
if (10 <= Integer.parseInt(s.substring(0, 2)) && Integer.parseInt(s.substring(0, 2)) <= 26)
dp[1] += 1;
for (int i = 2; i < num; i++) {
if (s.charAt(i - 1) == '0' && s.charAt(i) == '0') //当第三个字符为0时,如果第二个字符也为0时,就返回0。
return 0;
if (s.charAt(i) != '0')
dp[i] += dp[i - 1];
if (10 <= Integer.parseInt(s.substring(i - 1, i + 1)) && Integer.parseInt(s.substring(i - 1, i + 1)) <= 26)
dp[i] += dp[i - 2];
}
return dp[num - 1];
}
}
上一篇: 事务