把數(shù)字翻譯成字符串

題目描述

給定一個數(shù)字，我們按照如下規(guī)則把它翻譯為字符串：0 翻譯成 “a” ，1 翻譯成 “b”，……，11 翻譯成 “l(fā)”，……，25 翻譯成 “z”。一個數(shù)字可能有多個翻譯。請編程實現(xiàn)一個函數(shù)，用來計算一個數(shù)字有多少種不同的翻譯方法。

示例：

輸入: 12258
輸出: 5
解釋: 12258有5種不同的翻譯，分別是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

提示：
0 <= num < 231

轉(zhuǎn)載來源：力扣（LeetCode）

題目分析

這題和爬樓梯有點像，思路如下：

image

public int translateNum(int num) {
        int[] nums = split(num);
        int[] dp = new int[nums.length];
        if(dp.length == 1 || num == 0) return 1;
        dp[0] = 1;
        if(nums[0] == 1 || (nums[0] == 2 && nums[1] < 6))
            dp[1] = 2;
        else 
            dp[1] = 1;
        for(int i = 2; i < nums.length; i++){
            if(nums[i -1] == 1 || (nums[i-1] == 2 && nums[i] < 6)){
                dp[i] = dp[i-1] + dp[i-2];
            }else{
                dp[i] = dp[i-1];
            }
        }
        return dp[nums.length - 1];
    }
    
    public int[] split(int num){
        ArrayList<Integer> list = new ArrayList<>();
        while(num != 0){
            list.add(num % 10);
            num /= 10;
        }
        int[] nums = new int[list.size()];
        int index = nums.length - 1;
        for(Integer i:list){
            nums[index--] = i;
        }
        return nums;
    }