JZ46 把數字翻譯成字元串

描述

有一種將字母編碼成數字的方式：'a'->1, 'b->2', ... , 'z->26'。
現在給一串數字，返回有多少種可能的解碼結果

示例1
輸入： "12"
返回值：2
說明：  2種可能的解碼結果（”ab” 或”l”） 

思路

思路：

對於普通數組1-9，解碼方式只有一種，但是對於11-19，21-26，解碼方式有可選擇的兩種方案，因此我們使用動態規劃將兩種方案累計。

具體做法：

step 1：用輔助數組dp表示前i個數的解碼方法有多少種。
step 2：對於一個數，我們可以直接解碼它，也可以將其與前面的1或者2組合起來解碼：如果直接解碼，則dp[i]=dp[i−1]；如果組合解碼，則dp[i]=dp[i−2]。
step 3：對於只有一種解碼方式的，選上種dp[i−1]即可，對於滿足兩種解碼方式（10，20不能）則是dp[i−1]+dp[i−2]
step 4：依次相加，最後的dp[length]即為所求答案。

代碼

package mid.JZ46把數字翻譯成字元串;

import java.util.*;


public class Solution {
    /**
     * 解碼
     *
     * @param nums string字元串 數字串
     * @return int整型
     */
    public int solve(String nums) {
        // write code here
        //如果是0，直接排除
        if (nums.equals("0")) return 0;
        //如果是10 或者 20 就一種直接返回
        if (nums.equals("10") || nums.equals("20")) return 1;

        //如果後一位為0前一位不為1或者2 不行
        for (int i = 1; i < nums.length(); i++) {
            if (nums.charAt(i) == '0') {
                if (nums.charAt(i - 1) != '1' && nums.charAt(i - 1) != '2')
                    return 0;
            }
        }

        int[] dp = new int[nums.length() + 1];
        Arrays.fill(dp, 1);
        for (int i = 2; i <= nums.length(); i++) {
            if ((nums.charAt(i - 2) == '1' && nums.charAt(i - 1) != '0') || ((nums.charAt(i - 2) == '2' && (nums.charAt((i - 1)) > '0' && nums.charAt(i - 1) < '7'))))
                dp[i] = dp[i - 1] + dp[i - 2];
            else
                dp[i] = dp[i - 1];
        }
        return dp[nums.length()];
    }

    public static void main(String[] args) {
        System.out.println(new Solution().solve("12"));
    }
}