题解 | #把数字翻译成字符串#
思路:动态规划
如果没有 0 的话那就很简单了,直接按下面的递推公式遍历就行
dp[i] = dp[i - 1] + (i 和 i - 1 构成的数字是否合法 ? dp[i - 2] : 0);
但是输入的字符串可能会包含非法情况
这种情况一定是非法的
当前为 0,前面的不是 1 或 2.
因为如果不是 1,2 在前面,0 不可能和前面的凑起来也不可能和后面的凑起来,因此遇到这种情况就返回 0.
还有在递推时,当前字符为 0,就不能加上 dp[i - 1].因为单独的一个 0 不能译码
public int solve (String nums) { // 排除只有一个 0 的特殊情况 if ('0' == nums.charAt(0)) { return 0; } int[] dp = new int[nums.length() + 1]; dp[0] = 1; dp[1] = 1; Set<Character> validPrefix = new HashSet<>( Arrays.asList('1', '2') ); // 递推公式是: dp[i] = (当前字符是否为 0) ? 0 : dp[i - 1] + (i 和 i - 1 构成的数字是否合法 ? dp[i - 2] : 0); for (int i = 2; i < nums.length() + 1; i++) { int val = Integer.valueOf(nums.substring(i - 2, i)); dp[i] = (nums.charAt(i - 1) == '0' ? 0 : dp[i - 1]) + (val <= 26 && nums.charAt(i - 2) != '0' ? dp[i - 2] : 0); // 如果当前字符为 0,并且前面的不是 1或 2,那么这一串必定非法直接返回 0 if (nums.charAt(i - 1) == '0' && !validPrefix.contains(nums.charAt(i - 2))) { return 0; } } return dp[nums.length()]; }