【Leetcode】91. 解码方法(Decode Ways)
程序员文章站
2022-07-05 14:22:55
...
Leetcode - 91 Decode Ways (Medium)
题目描述:给定一个字符串,字母 A - Z 可以分别解码成 1 - 26,求字符串共有几种解码方法。
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
解题思路:要注意 0 的问题,0 在前面与在后面计算方式不同。从后向前递推能够减少对 0 情况的判断。
public int numDecodings(String s) {
int n = s.length();
if (n == 0) return 0;
int[] dp = new int[n + 1];
dp[n] = 1;
dp[n - 1] = s.charAt(n - 1) != '0' ? 1 : 0;
for (int i = n - 2; i >= 0; i--){
if (s.charAt(i) == '0') continue;
else dp[i] = (Integer.parseInt(s.substring(i, i + 2)) <= 26) ? dp[i + 1] + dp[i + 2] : dp[i + 1];
}
return dp[0];
}