Sword finger offer 46: Translate numbers into strings

Title Description ：

Given a number , We translate it as a string according to the following rules ：0 Translate into “a” ,1 Translate into “b”,……,11 Translate into “l”,……,25 Translate into “z”. A number may have more than one translation . Please program a function , Used to calculate how many different translation methods a number has .

Example 1:

Input : 12258

Output : 5

explain : 12258 Yes 5 Different translations , Namely "bccfi", "bwfi", "bczi", "mcfi" and "mzi"

solution ： Dynamic programming

Ideas ：

         This problem is similar to the problem of jumping steps , But there are additional restrictions . Assume a given number 122 There are three possibilities of translation ： The first one is bcc 122; The second kind bw 1 22 ; The third kind of mc 12 2.
        It can be observed that when traversing from left to right , There is a case of selecting one character or two characters Like jumping one or two spaces .  But the title gives limitations ：

• When you want to jump two spaces , The selected two digits meet >=10 And <=25
• When 0 As the leading digit of ten digits , Not an option

        If the appeal conditions are not met   There is no jumping two spaces You can only jump one space to reach the target . So when num[i-1,i] Spliced tens >=10 And <=25 when , Yes dp[i] = dp[i-1] + dp[i-2], That is, you can jump two spaces and one space . When num[i-1,i] Spliced tens >25 perhaps <10 when dp[i] = dp[i-1]   That is, you can only choose a scheme that jumps one grid .

therefore , Through the above analysis , The processing steps of this problem are as follows ：

• step 1： Use auxiliary array dp Before presentation i How many decoding methods are there .
• step 2： For a number , We can decode it directly , It can also be compared with the previous 1 perhaps 2 Combine to decode . If you decode directly , be dp[i]=dp[i−1]dp[i]=dp[i-1]dp[i]=dp[i−1]; If combined decoding ,dp[i]=dp[i−2]dp[i]=dp[i-2]dp[i]=dp[i−2].
• step 3： There is only one decoding method , Select a species dp[i−1]dp[i-1]dp[i−1] that will do , For satisfying two decoding methods （10,20 You can't ） It is dp[i−1]+dp[i−2]dp[i-1]+dp[i-2]dp[i−1]+dp[i−2]
• step 4： Add... In turn , final dp[length]dp[length]dp[length] That's the answer .

Code ：

class Solution {
    public int translateNum(int num) {
        // If the number is less than 10, Then there is only one translation result 
        if(num < 10){
            return 1;
        }
        // Convert numbers to character arrays 
        char[] chars = String.valueOf(num).toCharArray();
        // Auxiliary array of dynamic programming 
        int[] dp = new int[chars.length];
        // For the first number , As the first lattice for frogs to jump on the steps , And the first grid only has one skip , That is to say, it only corresponds to one translation result 
        dp[0] = 1;
        // Judge whether the second number can be carried out by skipping two spaces , That is, whether there are two translation results 
        dp[1] = chars[0]-'0' == 1 || (chars[0] - '0' ==2 && chars[1] - '0' < 6) ? 2 : 1;
        for(int i=2; i<dp.length; i++){
            int temp = chars[i-1] - '0';
            dp[i] = temp == 1 || (temp == 2 && chars[i] - '0' < 6) ? dp[i-1]+dp[i-2] : dp[i-1];
        }
        return dp[chars.length-1];
    }
}