[jz46 translate numbers into strings]

describe

There is a way to code letters into numbers ：'a'->1, 'b->2', ... , 'z->26'.
We encode a string into a string of numbers , Then consider reverse compiling into a string .
Because there is no delimiter , Encoding numbers into letters may have a variety of compilation results , for example 11 It can be seen as two 'a' It can also be seen as a 'k' . but 10 Can only be 'j' , because 0 Can't compile into any results .
Now give a string of numbers , Returns the number of possible decoding results

Data range ： The string length satisfies 0 < n ≤ 90
Advanced ： Spatial complexity O(n), Time complexity O(n)

Example 1

 Input ： "12"

 Return value ：2

 explain ：2 Possible decoding results （”ab”  or ”l”）    

Example 2

 Input ： "31717126241541717"

 Return value ：192

 explain ：192 Possible decoding results  

analysis ：

1. First, classify the data , For empty strings 、 The first character is ‘0’ String , as well as ‘0’ The previous one is not ‘1’ perhaps ‘2’ String , Output 0;

2. Create a dynamic array dp[len+1], Used to store several decoding results .dp[0]=1,dp[1]=1.

   1） Ruodi k Characters and the k-1 Characters can be combined into a To z Legal characters for , be dp[k+1]=dp[k]+dp[k-1];

   2） If it cannot form legal characters , The decoding result does not increase ,dp[k+1]=dp[k];

   3） Ruodi k Characters and the k-1 There are... In characters ‘0’, A new decoding method cannot be generated ,dp[k+1]=dp[k];

Code ：

class Solution {
    
    public:
    int solve(string nums) {
    
        int len = nums.size();
        if (len == 0)
            return 0;
        for (int k = 0;k < len;k++)
        {
    
            if (nums[k]=='0')
            {
    
                if (k == 0)
                    return 0;
                else if (nums[k-1] != '1' && nums[k-1] != '2')
                    return 0;
            }
        }// If 0 In the first place or 0 It's not in front of 1 perhaps 2, Decoding is not possible 
        int dp[len+1],temp;
        dp[0] = 1;
        dp[1] = 1;
        for (int k=1;k<len;k++)
        {
    
            temp=(nums[k]-'0')+(nums[k-1]-'0')*10;
            if (temp > 0 && temp <= 26 && nums[k]!= '0'&& nums[k-1] != '0')
                dp[k+1] = dp[k]+dp[k-1];
            else
                dp[k+1] = dp[k];
        }
        return dp[len];
    }
};

The elapsed time ：6ms
exceed 15.56% use C++ Submitted code
Take up memory ：424KB
exceed 46.36% use C++ Submitted code