面试题46. 把数字翻译成字符串

题目描述

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例：

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是”bccfi”, “bwfi”, “bczi”, “mcfi”和”mzi”

分析

  • 一开始想的也是 滑动窗口, 但后来想了一下不太正确，应该用动态规划

过程

以 nums = "12258" 为例子

  • i = 0, nums[0] => 1, 结果为b,那么结果只有一种， 解释： 只取第一个数1的时候，结果肯定只有一种，
    • 1 转成 b
  • i = 1, nums[1] => 2, 结果为bc, m, 那么结果有两种，解释： 当数字为12的时候，它可以为
    • 1 => b, 2 => c, 为一种：bc
    • 12 => m, 为一种：m
  • i = 2, nums[2] => 2, 结果为bcc, mc, bw, 结果有三种，解释：当数字为122的时候,它可以为
    • 1 => b, 2 => c, 2 => c 为一种, bcc
    • 12 => m, 2 => c 为一种, mc
    • 1 => b, 22 => w 为一种, bw
  • i = 3, nums[3] => 5, 结果为bccf, mcf, bwf, mz, bcz, 解释： 当数字为1225的时候，他可以为
    • 1 => b, 2 => c, 2 => c, 5 => f 为一种, bccf
    • 12 => m, 2 => c, 5 => f 为一种, mcf
    • 1 => b, 22 => w, 5 => f 为一种, bwf
    • 1 => b, 2 => c, 25 => z 为一中, bcz
    • 12 => m, 25 => z, 为一种：mz
  • i = 4, nums[4] => 8, 结果为bccfi, mcfi, bwfi, mzi, bczi, 解释： 当数字为12258的时候，他可以为
    • 1 => b, 2 => c, 2 => c, 5 => f, 8 => i 为一种, bccfi
    • 12 => m, 2 => c, 5 => f, 8 => i 为一种, mcfi
    • 1 => b, 22 => w, 5 => f, 8 => i 为一种, bwfi
    • 1 => b, 2 => c, 25 => z, 8 => i 为一中, bczi
    • 12 => m, 25 => z, 8 => i, 为一种：mzi

上面我们看 i = 1, i = 2, i = 3 的时候，的结果，我们用dp表示他们的结果
* i = 3的结果bccf, mcf, bwf, mz, bcz,
* i = 2的结果bcc, mc, bw,
* i = 1的结果m, bc

发现没，其实dp[3] 就是从 dp{2] 和dp[1]的结果过来的, dp[2]的字符串结果都加个f就等于dp[3]的前3个, dp[1]的字符串结果加个z就是dp[3]后三个
所以递推公式 dp[i] = dp[i - 1] + dp[i - 2], 但此时递推公式明显不符合i = 4的时候的值, dp[i] 明显等于 dp[i-1], 但前提是nums[i - 1] + nums[i] = 58 > 25

代码

var translateNum = function(num) {
    let numString = num + "";
    let length = numString.length;
    if(length < 1) {
        return 0
    }
    let dp = [];
    // 递推公式 dp[i] = d[i - 1] + dp[i - 2], 和 dp[i] = dp[i - 1]
    dp[0] = 1;
    for(let i = 1; i < length; i++) {
        const temp = numString[i - 1] + numString[i];  // 当temp = 06 的时候 其实也跟dp[i - 1]一样
        if(temp > 25 || numString[i - 1] == '0') {
            dp[i] = dp[i - 1]
        } else {
            dp[i] = dp[i - 1] + (i - 2 < 0 ? 1 : dp[i - 2]) ;  // i - 2 < 0 这里是为了解决 dp[i-2]防止溢出问题, 12 结果为2,
        }
    }
    return dp[length - 1]
};