leetcode|leetcode91. 解码方法 leetcode|LeetCode题解

题目一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1 'B' -> 2 ... 'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。
示例 1:

输入: "12" 输出: 2 解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。

【leetcode|leetcode91. 解码方法】示例 2:

输入: "226" 输出: 3 解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

解题

动态规划
从后向前解码

class Solution { public int numDecodings(String s) { int n = s.length(); // result[i] 表示字符串s的[i...s.length - 1)部分的解码结果数 int[] result = new int[n + 1]; char[] chars = s.toCharArray(); // 用于辅助倒数第二位的计算 result[n] = 1; // 以0开始的字符串无法进行解码 if (chars[n - 1] != '0'){ result[n - 1] = 1; }// 从后往前进行解码, f(n) = f(n + 1) + f(n + 2) // chars[n] == '0'时 f(n) = 0 // chars[n],chars[n + 1]组成的数字大于26时f(n) = f(n + 1) for (int i = n - 2; i >= 0; i--) { // 如果当前位为0, 则结果为0 ,不需要进行解码 if (chars[i] != '0') { if (Integer.parseInt(s.substring(i, i + 2)) <= 26) { result[i] = result[i + 1] + result[i + 2]; } else { result[i] = result[i + 1]; } } }return result[0]; } }