This is the 17th day of my participation in Gwen Challenge

The topic of dry

A message containing the letters A-Z is encoded by the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
Copy the code

To decode the encoded message, all numbers must be mapped back to letters, based on the above method of mapping (there may be several methods). For example, “11106” can be mapped to:

"AAJF", which groups the messages into (11 10 6) "KJF", which groups the messages into (11 10 6)Copy the code

Note that messages cannot be grouped as (1 11 06) because “06” cannot be mapped to “F”, since “6” and “06” are not equivalent in the mapping.

Given a non-empty string s containing only numbers, count and return the total number of decoding methods.

The data guarantees that the answer is a 32 – digit integer.

Example 1:

Input: s = "12" Output: 2 Explanation: It can be decoded as either "AB" (1, 2) or "L" (12).Copy the code

Solution: dynamic programming

First of all, the general idea of the topic is to let us corresponding to the number of transcoding, statistics can be the most transcoding number. We also need to consider some boundary problems, such as when the number is 0 or when the concatenation of arrays is greater than 26.

First of all, the meaning of our DP array is that there are dp[I] decoding methods available at I.

Let’s first try to simulate a group and see if we can derive a recursive formula for it:

1226
6->dp[i]=1
26->dp[i]=2
226->dp[i]=3
1226->dp[i]=5
Copy the code

When we traverse backwards and forwards, our recursive formula is actually:

dp[i]=dp[i+1]+dp[i+2]
Copy the code

Of course, we also need to consider the following situation when the current element is 0

1206
6->dp[i]=1
06->dp[i]=0
206->dp[i]=1
1206->dp[i]=1
Copy the code

So dp[I] is equal to 0 when the current element is 0.

Another case is when out of range:

1186
6->dp[i]=1
86->dp[i]=1
186->dp[i]=2
1286->dp[i]=3
Copy the code

So we can write our code:

Note that our dp array should be initialized with one more element than the array, and the last element is initialized to 1 for subsequent iteratively added operations.

Execution time: 72 ms, beating 99.47% of all JavaScript commits

Memory consumption: 39.4 MB, beating 59.15% of all JavaScript commits

/ * * *@param {string} s
 * @return {number}* /
var numDecodings = function (s) {
    // the dp array represents all qualified values starting from s
    let len = s.length;
    let dp = new Array(len + 1).fill(0)
    dp[len] = 1;
    dp[len - 1] = 1;
    // Determine whether the last element of the dp array is 0, if so, set the last element of the dp array to 0
    if (s[len - 1] = =0) {
        dp[len - 1] = 0
    }
    // Start traversing the dp array forward
    for (let i = len - 2; i >= 0; i--) {
        // If the element is 0, the current dp value is 0
        if (s[i] == '0') {
            dp[i] = 0
            continue
        }
        // If the current element is a value that does not fit the range
        let currentindex = s[i] - '0';
        let nextindex = s[i + 1] - '0';
        let theNumber = currentindex * 10 + nextindex
        // Store the second part of the dynamic gauge equation
        let temp = 0;
        if (theNumber <= 26) {
            temp = dp[i + 2]
        }
        dp[i] = dp[i + 1] + temp
    }
    return dp[0]};Copy the code