有一个消息包含A-Z通过以下规则编码
'A' -> 1
'B' -> 2
...
'Z' -> 26
现在给你一个加密过后的消息,问有几种解码的方式
样例
样例 1:
输入: "12"
输出: 2
解释: 它可以被解码为 AB (1 2) 或 L (12).
样例 2:
输入: "10"
输出: 1
注意事项
我们不能解码空串,因此若消息为空,你应该返回0。
消息的长度 n ≤ 100
/**
* @param s: a string, encoded message
* @return: an integer, the number of ways decoding
*/
public static int numDecodings(String s) {
// write your code here
int n = s.length();
if (n == 0) {
return 0;
}
char[] chars = s.toCharArray();
int[] f = new int[n + 1];
f[0] = 1;
for (int i = 1; i <= n; i++) {
f[i] = 0;
if (chars[i - 1] > '0' && chars[i - 1] <= '9') {
f[i] += f[i - 1];
}
if (i > 1) {
int j = 10 * (chars[i - 2] - '0') + (chars[i - 1] - '0');
if (j >= 10 && j <= 26) {
f[i] += f[i - 2];
}
}
}
return f[n];
}
网友评论