[LeetCode每日一题]91. Decode Ways

题目如下:

A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example:
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

A-Z分别编码成1-26,给定一串编码后的数字串,问我们有多少种合法的解码方法。
这道题可以用动态规划的方法解决,解题思路和LeetCode-70爬楼梯问题类似定义状态空间dp[i]表示从第1个到第i个数字的解码方法,求解状态空间时有以下两种情况:
1.第i个字符单独解码,则dp[i] == dp[i-1];
2.第i个字符和第i-1个字符一同解码,则dp[i] == dp[i-2]。
综合考虑以上两种情况以及边界条件,代码如下:

  1. class Solution {
  2. public int numDecodings(String s) {
  3. if (s.isEmpty() || s.charAt(0) == '0') {
  4. return 0;
  5. }
  6. int[] dp = new int[s.length() + 1];
  7. dp[0] = 1;
  8. dp[1] = 1;
  9. for (int i = 2; i <= s.length(); i++) {
  10. char one = s.charAt(i - 1);
  11. int two = Integer.parseInt(s.substring(i - 2, i));
  12. if (one != '0') {
  13. dp[i] += dp[i - 1];
  14. } else {
  15. if (s.charAt(i - 2) > '2' || s.charAt(i - 2) == '0') {
  16. return 0;
  17. }
  18. }
  19. if (two >= 10 && two <= 26) {
  20. dp[i] += dp[i - 2];
  21. }
  22. }
  23. return dp[s.length()];
  24. }
  25. }

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注