题目

给定一个数字,按照如下规则翻译成字符串:0 翻译成“a”,1 翻译成“b”25翻译成“z”。一个数字有多种翻译可能,例如12258一共有5种,分别是bccfibwfibczimcfimzi。实现一个函数,用来计算一个数字有多少种不同的翻译方法。

解题思路

  1. 定义 f(i)f(i) 表示第 i 位有多少种翻译的方法,动态规划方程:f(i)=f(i+1)+g(i,i+1)×f(i+2)f(i)=f(i+1)+g(i,i+1) \times f(i+2)
  2. 其中 g(i,i+1)g(i,i+1) 表示 i,i+1 是否能组成 10 ~ 25
public int translateNumToStr(int num) {
    char[] str = String.valueOf(num).toCharArray();
    int[] res = new int[str.length];

    for (int i = str.length - 1; i >= 0; i--) {
        if (i + 1 >= str.length) {
            res[i] = 1;
            continue;
        }

        res[i] = res[i + 1];

        if (i + 2 < str.length && str[i] <= '2' && str[i] >= '1' && str[i + 1] <= '5') {
            res[i] += res[i + 2];
        }
    }
    return res[0];
}

results matching ""

    No results matching ""