This article originated from personal public account: TechFlow, original is not easy, for attention


Today is the 57th article in LeetCode. Let’s take a look at LeetCode’s question 91, Decode ways.

The official difficulty of this question is Medium, with 2680 thumbs up and 2845 thumbs down, with a pass rate of 24.5%. Judging from the pass rate, this question seems to be difficult, even more difficult than many Hard questions. Judging by the number of upvotes and downvotes, this question seems to be mixed, with a large number of people on both sides. Generally speaking, the evaluation of the topic is one-sided, which rarely occurs. The first thing worth saying is that I personally definitely think it’s worth doing, but is it a good question? I’ll leave that to you.

First of all, let’s look at the meaning of this problem.

The question

We can map letters to numbers when sending messages, such as A to 1, B to 2, and Z to 26. We’re going to assume that we’re using only capital letters, which means we can use 26 numbers to represent all letters from A to Z.

Now we have a string of numbers and want to restore it to the original letter information. How many ways can we restore it?

The sample

Input: "12"

Output: 2

Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Copy the code
Input: "226"

Output: 3

Explanation: It could be decoded as "BZ"26 (2),"VF" (22 6), or "BBF"(2, 2, 6).

Copy the code

Answer key

Let’s look at an example. For example, 12 can be read as the character 12, which is L, or it can be read as the concatenation of 1 and 2. Similarly, 226 has three reduction methods, namely, (2, 2, 6), (22, 6), (2, 26). We just need to return all possible quantities.

The problem seems to have no clue, but when we take a closer look at what’s going on, it’s really not that complicated. First of all, there are only 10 possibilities from 0 to 9 for each digit in the string. First of all, if it is 0, since our A maps to 1, 0 can only be 10 or 20 with the preceding digit. If the preceding digit is not 1 or 2, then the string is illegal, which means there is no way to restore it.

If a digit is a number between 1 and 9, it can be a single letter. And let’s think about the preceding digit, the preceding digit is only one and two of these two possibilities that can form a new component. Note that if the first digit is a 2, the current digit must be less than 6, because the letter does not go up to 26. So there’s a special judgment to be made here, but there’s nothing else.

Once these possibilities are enumerated, the rest is easy, for example, we can use deep search to find all the possible solutions. Since we’ve enumerated all the cases, this code isn’t hard to write, but it’s not easy to get it right the first time either.

class Solution:

    def numDecodings(self, s: str) -> int:

        n = len(s)

        ret = 0

        

        def dfs(i):

            nonlocal ret

            

            if i >= n:

                ret += 1

                return 

            

            # if the current bit is 0, there is no solution

            The current bit is 0, indicating that the previous bit is not 1 or 2

            if s[i] == '0':

                return

            

            # Recurse to a single case

            dfs(i+1)

            

            # Determine if the next digit can form a combination

            if i+1 < n and (s[i] == '1' or (s[i] == '2' and ord(s[i+1]) <= ord('6'))) :

                dfs(i+2) 

                

        dfs(0)

        return ret

Copy the code

The search algorithm can be solved, but it must time out. It’s not hard to see that when our string length is large, the possibilities for solutions are very large. In the most extreme cases, if each digit is a 1, it can either stand alone as a character or be combined with the next digit to form an 11 to form a new character. The total number of cases is increasing by Fibonacci, and n doesn’t have to be very large to bring in an astronomical number of solutions.

With search algorithms we need to exhaust every case, and even the complexity required to find every solution is overwhelming.

So we have to think of a better way, and it’s not hard to think of a better way, which is dynamic programming.

If we analyze it, we’ll see that the solutions that each digit can form depend only on the preceding digit, and nothing on the following digit. This is obviously to meet the dynamic programming without aftereffect. That is, the previous character combination does not affect the subsequent solution.

We assume that dp[I] stores the number of solutions made up of the first I numbers, and there are 10 cases for S [I], 0 through 9. If s[I] is 0, then s[I -1] if it is 1 or 2, there is only one case where 0 and s[I -1] form 10 or 20. So dp[I] = dp[I -2].

If s[I] is not 0, then s[I] can choose to be a single character, then dp[I] = dp[i-1]. Of course, if s[i-1] is 1 or 2, s[I] can be combined with s[i-1] to form a single character. In this case, dp[I] needs to add dp[i-2], that is, the possibility of the answer formed by DP [I] increases.

If you tease out the transitions between these states, the code should not be difficult to write.

class Solution:

    def numDecodings(self, s: str) -> int:

        n = len(s)

        # To simplify our judgment, we prefix s with 0 so that the string subscript starts at 1

        s = '0' + s

        dp = [0 for _ in range(n+2)]

        

        dp[0] = 1

        for i in range(1, n+1) :

            If the current bit is 0, check whether the previous bit is 1 or 2

            Otherwise there must be no solution

            if s[i] == '0':

                if i > 1 and s[i- 1] in ('1'.'2') :

                    dp[i] = dp[i2 -]

                else:

                    return 0

                continue

            dp[i] = dp[i- 1]

            # to form a character with the preceding digit, add the number dp[i-2]

            if i > 1 and s[i- 1] = ='1' or s[i- 1] = ='2' and ord(s[i]) <= ord('6') :

                dp[i] += dp[i2 -]

        return dp[n]

Copy the code

conclusion

From the point of view of dynamic programming, this problem is not difficult, it is easy to solve. But if you don’t think about dynamic programming, if you don’t think about search algorithms then you probably won’t be able to do AC all the time.

I do not know whether the poor comments are the latter situation, but purely from the quality of the problem, the quality of this problem is good, is a very good connection dynamic programming exercises, so I suggest you have time to experience.

This is the end of today’s article, if you like this article, please invite a wave of quality sanlian, give me a little support (follow, forward, like).

– END –