把数字翻译成字符串

题目

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

解题思路

  1. 定义 $$f(i)$$ 表示第 i 位有多少种翻译的方法,动态规划方程:$$f(i)=f(i+1)+g(i,i+1) \times f(i+2)$$
  2. 其中 $$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];
    }