有一个消息包含?A-Z?通过以下规则编码
‘A‘ -> 1
‘B‘ -> 2
...
‘Z‘ -> 26
现在给你一个加密过后的消息，问有几种解码的方式
- 我们不能解码空串，因此若消息为空，你应该返回0。
- 消息的长度 n≤100
样例 1:
输入: "12"
输出: 2
解释: 它可以被解码为 AB (1 2) 或 L (12).
样例 2:
输入: "10"
输出: 1
算法思路
- 对于一段编码?s?，设他有?x?种解码，如果在?s?后面加上一个个位数，那么获得的编码就拥有?s?的这?x?种解码方式(不仅限于这?x?种)；如果在后面加上一个小于等于26的两位数，那么同理可得，获得的编码就拥有?s?的这?x?种解码方式(不仅限于这?x?种)。
- 因此我们可以用动态规划的方式来解决这个问题
代码思路
- 状态：?dp[i]?表示字符串的前?i?位解码有多少种解码方式
- 初始化：?dp[0] = dp[1] = 1?，dp数组其他值均为0，
- 状态转移方程
- 若?s[i - 1]?表示的数是1到9，?dp[i] += dp[i - 1]?
- 若?s[i - 2]?和?s[i - 1]?表示的数是10到26，?dp[i] += dp[i - 2]?
- 若上述两种情况都不满足，直接返回答案0
复杂度分析
N表示字符串长度
- 空间复杂度：O(N) 可以用滚存优化到O(1)
- 时间复杂度：O(N)
public class Solution {
* @param s: a string, encoded message
* @return: an integer, the number of ways decoding
*/
public int numDecodings(String s) {
if (s.length() == 0 || s.charAt(0) == ‘0‘) {
return 0;
}
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) {
if (s.charAt(i - 1) != ‘0‘) {
dp[i] += dp[i - 1];
}
if (s.charAt(i - 2) != ‘0‘ && (s.charAt(i - 2) - ‘0‘) * 10 + s.charAt(i - 1) - ‘0‘ <= 26) {
dp[i] += dp[i-2];
}
if (dp[i] == 0) {
return 0;
}
}
return dp[n];
}
}
[leetcode/lintcode 题解] Google 面试题：解码方法
原文：https://www.cnblogs.com/lintcode/p/14078218.html
