This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

1. Title Description

The decoding method

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”, groups the messages into (11 10 6) “KJF”, groups the messages into (11 10 6) note that the messages cannot be grouped into (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.

Second, train of thought analysis

• This problem examines the problem of dynamic programming. The so-called dynamic programming is to simplify big problems into small problems so as to solve big problems.
• In fact, the solution idea of dynamic programming is fixed, and the solution idea is summed up in a word: transfer from large to small, and solve the problem from childhood

Transfer equation

• The so-called transfer equation is the transfer from large to small. If you want to go from a big problem to a small problem, there must be a basis for the transition
• Whether a dynamic programming can be completed depends mainly on the setting of the transfer equation. You can’t do dynamic programming if you don’t understand the transfer equation.
• First we have decoded the number 1121 as an example. Because the maximum number of codes in this case is z–>26. 26 is a two-digit number so 1121 ends up adding at most two digits

• So the number of possible 1121 decodes depends on the 112 and 11 codes. If we set Fx to represent the number of decodes that the x-th bit exists we can get the following formula

• This is the way to think about it if it’s a little bit sudden. First of all, it’s impossible to have consecutive zeros in the code. This condition exists because there is no mapping of 00 in the encoding table and the maximum mapping number is 26
• If the current number is not zero, it must correspond to a number in the encoding table. So his combination will contain the number of decodes of the previous string
• The current number that is not zero and consists of two digits within 26 means that the mapping can also be found in the code table so the current decoded number also contains the previous decoded number of the previous one
• And the number of different characters decoded does not affect each other. That’s why F of x is equal to F of x minus 1 plus F of x minus 2. This is, of course, subject to certain conditions

The initial value

• Change from a big problem to a small problem. Finally, through solving small problems to achieve the final solution of the big problem. Refinement to what point is the refinement termination state? It must be refined to an initial state.
• In this case, the initial state is null. When the code is a blank is the corresponding decoding nature is empty. And empty is our initial value
• We defined Fx above as the number of decodes up to the x-th bit. And the natural equivalent of what we call empty is F0. And empty is empty when decoded. So the F0 = 1

• F (0) is a null character, and in fact f(1)=1 is the initial value at the first character. But let’s say that f of 1 is a variable in terms of the problem or in terms of the test case. Why do you say that?
• Because it’s in the test case0or06Wait for the data. These numbers don’t match because of 0. In the mapping table, only numbers that end in 0 cannot have numbers that begin with 0. So f of 1 is equal to 0
• So f(1) requires the calculation of the parameter transfer equation. But the first two of f(1) are f(-1), so in order to keep the array from going out of bounds we need to put a conditional on it

From childhood to calculation

• With the transfer equation and the initial values settled, all that remains is for us to start iterating. The iterative process is the process of implementing from small to large

AC code

// Special fast processing
if (0==s.length()) {
    return 0;
}
// Build a code to store the number of decodes generated previously; For transfer equations
int[] countArr = new int[s.length()+1];
/ / initial value
countArr[0] = 1;
for (int i = 1; i <= s.length(); i++) {
    //chart to int char-'0'
    int sint = s.charAt(i-1) -'0';
    if(sint ! =0) {
        countArr[i] += countArr[i - 1];
    }
    // The first element needs to be filtered
    if(i>1&&s.charAt(i-2)! ='0'&&(s.charAt(i-2) -'0') *10+(s.charAt(i-1) -'0') < =26){
        countArr[i] += countArr[i - 2]; }}return countArr[s.length()];
Copy the code

• The execution speed is still pleasing to the eye. Memory consumption is also acceptable. But we are confident that we do not need to open up a number to store the decoding number of each node for this problem. We’re going to use the first two states at most. So we can specifically open up two variable stores. Open up a variable to store the current decoded number.

public int numDecodings(String s) {
    if (0==s.length()) {
        return 0;
    }
    int pre =1;
    int prepre = 0;
    int current = 0;
    for (int i = 1; i <= s.length(); i++) {
        current = 0;
        int sint = s.charAt(i-1) -'0';
        if(sint ! =0) {
            current = pre;
        }
        if(i>1&&s.charAt(i-2)! ='0'&&(s.charAt(i-2) -'0') *10+(s.charAt(i-1) -'0') < =26){
            current += prepre;
        }
        prepre = pre;
        pre = current;
    }
    return pre;
}
Copy the code

Four,

• Dynamic programming is an inescapable obstacle in algorithms. If you want to learn anything from algorithms, you have to master dynamic programming thoroughly.
• To be honest, I am not familiar with dynamic programming. Every time in the high difficulty of dynamic programming it is difficult to accurately clarify the transfer equation.
• The revolution has not yet succeeded, and comrades still have work to do.

collection