Piecewise linear DP problem, as well as common spatial optimization means | Java brush problem punch card

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

Topic describes

This is the 91. decoding method on LeetCode with medium difficulty.

Tag: “Linear DP”

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”, grouping messages into (1, 1, 10, 6)
• “KJF”, grouping messages into (11, 10, 6)

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

Example 2:

Input: s = "226" Output: 3 Explanation: It can be decoded to "BZ" (2 26), "VF" (22 6), or "BBF" (2 26).Copy the code

Example 3:

Input: s = "0" Output: 0 Description: No character maps to a number starting with 0. Valid mappings with 0 are 'J' -> "10" and 'T'-> "20". Since there are no characters, there is no efficient way to decode this because all numbers need to be mapped.Copy the code

Example 4:

Input: s = "06" Output: 0 Explanation: "06" cannot be mapped to "F" because the string contains a leading 0 ("6" and "06" are not equivalent in mapping).Copy the code

Tip:

• 1 <= s.length <= 100
• S contains only numbers and may contain leading zeros.

---

Fundamental analysis

We call a decoded content an item.

Each item can be composed of either one or two numbers, depending on the question.

Data range is 100, very confusing, there may be a lot of students want to use DFS search.

We can take a look at whether this is possible: Without loss of generality, any position I in the string S can be either an independent item or a new item formed with the previous position, so there are two segmentation options for each position (regardless of the legitimacy of segmentation results). The complexity of doing this is O(2n)O(2^n)O(2n), when n is 100, far more than our computer can do in a single second (10710^7107). Even if we put the operation of “judging whether the segmentation result is legal” in the process of explosion search to do pruning, it is far from our maximum computation in one second.

The recursive method is not feasible, we need to consider the recursive solution.

---

Dynamic programming

This is actually a string class dynamic programming problem, it is not difficult to find for stringssA certain position ofiWe only care about locationiCan form their own independenceitem“And” LocationiBe able to compete with the previous position (i-1) can formitem“Rather than carei-1The previous position.

Given the above analysis, we can process the string S backwards, using an array to record the number of decoding schemes ending in each bit of the string S. That is, f[I]f[I]f[I] is defined as the number of decoding schemes considering the first iii characters.

For any position I of string s, there are three cases:

• Only by locationiAlone as oneitem, is set toaThe premise of transfer isaThe value range of is
  $[1, 9]$, the transfer logic is
  $f[i] = f[i – 1]$.
• Only by locationiAnd the previous position (i-1) together as oneitem, is set tobThe premise of transfer isbThe value range of is
  $[10, 26]$, the transfer logic is
  $f[i] = f[i – 2]$.
• locationiCan act as independenceitemIt can also form with the previous positionitem, the transfer logic is
  $f[i] = f[i – 1] + f[i – 2]$.

Therefore, we have the following transfer equation:

Other details: There are leading zeros in the topic, and leading zeros are invalid items. Special judgment can be carried out, but I am used to append space to the head of the string as a sentinel. Append space can not only avoid the discussion of leading zero, but also make the subscript start from 1, simplifying the judgment of f[i-1] and other negative subscripts.

Code:

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        s = "" + s;
        char[] cs = s.toCharArray();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) { 
            // a: indicates "current position" to form item separately
            // b: represents "current position" and "previous position" together to form item
            int a = cs[i] - '0', b = (cs[i - 1] - '0') * 10 + (cs[i] - '0');
            // if a is valid, then f[I] can be transferred from f[i-1]
            if (1 <= a && a <= 9) f[i] = f[i - 1];
            // If b is valid, then f[I] can be transferred from f[i-2] or f[i-1] &f [i-2]
            if (10 <= b && b <= 26) f[i] += f[i - 2];
        }
        returnf[n]; }}Copy the code

• Time complexity: SharednThree states need to be transferred. Complexity of
  $O(n)$.
• Space complexity: O(n)O(n)O(n).

---

Space optimization

It is not difficult to find that we only rely on the two states f[i-1] and F [i-2] when transferring F [I].

So we can take a similar approach to scrolling arrays, just create arrays of length 3, and use subscripts that are no longer needed by mod.

Code:

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        s = "" + s;
        char[] cs = s.toCharArray();
        int[] f = new int[3];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            f[i % 3] = 0;
            int a = cs[i] - '0', b = (cs[i - 1] - '0') * 10 + (cs[i] - '0');
            if (1 <= a && a <= 9) f[i % 3] = f[(i - 1) % 3];
            if (10 <= b && b <= 26) f[i % 3] += f[(i - 2) % 3];
        }
        return f[n % 3]; }}Copy the code

• Time complexity: SharednThree states need to be transferred. Complexity of
  $O(n)$.
• Space complexity: O(1)O(1)O(1).

---

The last

This is the No.91 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode as of the start date, some of which have locks, so we will finish all the topics without locks first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.