Detailed explanation of the decoding method example of Go Java algorithm

Decoding method

A message containing the letter A-Z is encoded with the following mapping:

• 'A' -> "1"
• 'B' -> "2"
• ...
• 'Z' -> "26"

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

"AAJF" , group messages into (1 1 10 6)

"KJF" , group messages into (11 10 6)

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

Give you a non-empty string s containing only numbers, and calculate and return the total number of decoding methods.

The answer to the question is guaranteed to be a 32-bit integer.

• Example 1:

Enter: s = "12"

Output: 2

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

• Example 2:

Input: s = "226"

Output: 3

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

• Example 3:

Enter: s = "0"

Output: 0

Explanation: No characters are mapped to numbers starting with 0.

Valid maps containing 0 are 'J' -> "10" and 'T'-> "20" .

Since there are no characters, there is no efficient way to decode this, as all numbers need to be mapped.

hint:

1 <= <= 100

s contains only numbers and may contain leading zeros.

Method 1: Dynamic Programming (Java)

For a given string s, let its length be n, and the characters from left to right are s[1], s[2],..., s[n]. We can use dynamic programming methods to calculate the number of decoding methods of a string.

Specifically, let fi represents the number of decoding methods for the first i characters s[1..i] of the character string s. When doing state transfer, we can consider which characters in s were used for the last decoding.

class Solution {
    public int numDecodings(String s) {
        int n = ();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if ((i - 1) != '0') {
                f[i] += f[i - 1];
            }
            if (i > 1 && (i - 2) != '0' && (((i - 2) - '0') * 10 + ((i - 1) - '0') <= 26)) {
                f[i] += f[i - 2];
            }
        }
        return f[n];
    }
}

Time complexity: o(n)

Space complexity: o(n)

Method 2: Dynamic programming—optimization (go)

For specific methods, please refer to the above statement. This method optimizes the spatial complexity. By using temporary variables, the spatial complexity is reduced from o(n) to o(1)

func numDecodings(s string) int {
    n := len(s)
    // a = f[i-2], b = f[i-1], c = f[i]
    a, b, c := 0, 1, 0
    for i := 1; i <= n; i++ {
        c = 0
        if s[i-1] != '0' {
            c += b
        }
        if i > 1 && s[i-2] != '0' && ((s[i-2]-'0')*10+(s[i-1]-'0') <= 26) {
            c += a
        }
        a, b = b, c
    }
    return c
}

Time complexity: o(n)

Space complexity: o(1)

The above is a detailed explanation of the example decoding method of Go Java algorithm. For more information about Go Java algorithm decoding, please pay attention to my other related articles!