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 1:
Input: "12"Output: 2Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: "226"Output: 3Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
难度：medium
题目：一则数字消息由Ａ到Ｚ的字符编码，字符与数字的匹配关系如下
'A' -> 1'B' -> 2...'Z' -> 26
给定非空字符串仅包含数字，判断它由多少种解码方式。
思路：动态规划，首先来分解一下问题
状态转移方程f(n) = f(n - 1) + f(n - 2) 当前字符在［1,9] 之间，且当前字符与前一字符组成的数在［11,19]［21,26]之间f(n) = f(n - 1) 当前字符与前一字符组成的数不在［1,9]［11,26]之间f(n) = f(n - 2) 当前字符与前一字符组成的数为10或20
根据此方程可以使用递归实现，这是将想法实施的第一步。
第二步优化，将递归实现转成迭代实现。Runtime: 5470 ms, faster than 0.99% of Java online submissions for Decode Ways.
Memory Usage: 50.2 MB, less than 0.97% of Java online submissions for Decode Ways.class Solution { public int numDecodings(String s) { return numDecodings(s, s.length()); } // length > 0 private int numDecodings(String s, int length) { // 字符不为空 初始化length0 为1 if (0 == length) { return 1; } if (1 == length) { if (Integer.parseInt(s.substring(length - 1, length)) > 0) { return 1; } return 0; } int last = length - 1; int prev = last - 1; int valLast = Integer.parseInt(s.substring(last, last + 1)); int valPrev = Integer.parseInt(s.substring(prev, prev + 2)); if (10 == valPrev || 20 == valPrev) { return numDecodings(s, length - 2); } else if (valPrev >= 10 && valPrev <= 26) { return numDecodings(s, length - 1) + numDecodings(s, length - 2); } if (valLast > 0 && valLast < 10) { return numDecodings(s, length - 1); } return 0; }} Runtime: 3 ms, faster than 43.60% of Java online submissions for Decode Ways.
Memory Usage: 34.6 MB, less than 3.09% of Java online submissions for Decode Ways.class Solution { public int numDecodings(String s) { if (s.charAt(0) == '0') { return 0; } int p = 1, q = 1, result = 1; for (int i = 1; i < s.length(); i++) { int num1 = s.charAt(i) - '0'; int num2 = Integer.valueOf(s.substring(i - 1, i + 1)); if (num2 == 10 || num2 == 20) { result = p; } else if (10 < num2 && num2 <= 26) { result = p + q; } else if (num1 > 0 && num1 < 10) { result = q; } else { return 0; } p = q; q = result; } return result; }}