剑指Offer Java版 面试题46：把数字翻译成字符串

题目：给定一个数字，我们按照如下规则把它翻译为字符串：0翻译成“a”，1翻译成“b”，……，11翻译成“l”，……，25翻译成“z”。一个数字可能有多个翻译。例如，12258有5种不同的翻译，分别是“bccfi”、“bwfi”、“bczi”、“mcfi”和“mzi”。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

参考答案

public int getTranslationCount(int number) {
    if (number < 0) {
        return 0;
    }
    String numberStr = String.valueOf(number);
    int[] counts = new int[numberStr.length()];
    counts[0] = 1;
    for (int i = 1; i < counts.length; i++) {
        counts[i] = counts[i - 1];
        int converted = (numberStr.charAt(i - 1) - '0') * 10 + numberStr.charAt(i) - '0';
        if (converted >= 10 && converted < 26) {
            if (i - 2 >= 0) {
                counts[i] += counts[i - 2];
            } else {
                counts[i]++;
            }
        }
    }
    return counts[counts.length - 1];
}

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(n)。

👉剑指Offer Java版目录
👉剑指Offer Java版专题