Go Javaアルゴリズムのデコード方法のサンプルコード分析

デコード方法

文字 A ～ Z を含むメッセージは、次のマッピングでエンコードされます:

• ##'A' -> "1"

• 'B' -> "2"

• ...

• 'Z' -> " 26 "

エンコードされたメッセージをデコードするには、上記でマッピングされた方法に基づいて、すべての数字を文字にマッピングし直す必要があります (方法は複数ある場合があります)。たとえば、「11106」は次のようにマッピングできます:

"AAJF" 、メッセージを (1 1 10 6)

"KJF" としてグループ化、メッセージを (11 10 6)## としてグループ化

#「6」と「06」はマッピングにおいて同等ではないため、「06」を「F」にマッピングできないため、メッセージを (1 11 06) としてグループ化できないことに注意してください。

数値のみを含む空ではない文字列 s が与えられた場合、デコード メソッドの合計数を計算して返してください。

質問データにより、回答が 32 ビット整数であることが保証されます。

#例 1:

• #入力: s = "12"

出力: 2

説明: 「AB」 (1 2) または「L」 (12) としてデコードできます。

#例 2:

• 入力: s = "226"

出力: 3

説明: 「BZ」(2 26)、「VF」(22 6)、または「BBF」(2 2 6) としてデコードできます。

#例 3:

#入力: s = "0"

• 出力: 0

説明: 0 で始まる数値にマップされる文字はありません。

0 を含む有効なマッピングは、 'J' -> "10" および 'T'-> "20" です。

文字がないため、すべての数値をマッピングする必要があるため、これをデコードする効率的な方法はありません。

ヒント:

1

s には数字のみが含まれ、先頭にゼロが含まれる場合があります。

方法 1: 動的プログラミング (Java)

指定された文字列 s について、その長さを n とし、その中の文字は左から右に s[1],s [2] とします。 ]、...、s[n]。動的プログラミングを使用して、文字列のデコード メソッドの数を計算できます。

具体的には、文字列 s の最初の i 文字 s[1..i] の復号化メソッドの数を fi とします。状態転送を実行するとき、s 内のどの文字が最後のデコードに使用されたかを考慮できます。

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];
    }
}

時間計算量: o(n)

空間計算量: o(n)

方法 2: 動的プログラミング - 最適化 (go)

具体的な方法のアイデアについては、上記の説明を参照してください。この方法は、空間の複雑さを最適化します。一時変数を使用することで、空間の複雑さを o(n) から o(n) に削減します。 (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
}

時間計算量: o(n)

空間計算量: o(1)

以上がGo Javaアルゴリズムのデコード方法のサンプルコード分析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。