Go Java algorithm decoding method example code analysis

Decoding method

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

• ##'A' -> "1"

• 'B' -> "2"

• ...

• 'Z' -> " 26"

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

"AAJF" , grouping messages as (1 1 10 6)

"KJF" , grouping messages as (11 10 6)

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

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

The question data ensures that the answer must be a 32-bit integer.

• Example 1:

Input: 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:

Input: s = "0"

Output: 0

Explanation: No character maps to a number starting with 0.

Valid mappings 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.

Tip:

1 <= s.length <= 100

s contain only digits and may contain leading zeros.

Method 1: Dynamic Programming (Java)

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

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

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

Time complexity: o(n)

Space complexity: o(n)

Method Two: Dynamic Programming - Optimization (go)

Please see the above description for specific method ideas. This method optimizes the space complexity. By using temporary variables, Reduce the space complexity 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] != &#39;0&#39; {
            c += b
        }
        if i > 1 && s[i-2] != &#39;0&#39; && ((s[i-2]-&#39;0&#39;)*10+(s[i-1]-&#39;0&#39;) <= 26) {
            c += a
        }
        a, b = b, c
    }
    return c
}

Time complexity: o(n)

Space complexity: o(1)

The above is the detailed content of Go Java algorithm decoding method example code analysis. For more information, please follow other related articles on the PHP Chinese website!