この問題の説明から始めましょう:

数字の文字列としてエンコードされた秘密メッセージを傍受しました。メッセージは次のマッピングによってデコードされます:

"1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z'

しかし、メッセージを解読していると、一部のコードは他のコードに含まれているため、メッセージを解読するさまざまな方法があることがわかります (「2」と「5」対「25」)。

たとえば、「11106」は次のようにデコードできます:

• グループ化 (1、1、10、6) の「AAJF」
• グループ化 (11、10、6) の「KJF」
• 「06」は有効なコードではないため、グループ化 (1、11、06) は無効です (有効なのは「6」のみです)。

注: デコードできない文字列が存在する可能性があります。

数字のみを含む文字列 s を指定すると、それを デコードするための 方法の数を返します。文字列全体を有効な方法でデコードできない場合は、0.

を返します。

テスト ケースは、答えが 32 ビット 整数に収まるように生成されます。

例えば：

Input: s = "12"

Output: 2

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

または：

Input: s = "226"

Output: 3

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

または：

Input: s = "06"

Output: 0

Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06"). In this case, the string is not a valid encoding, so return 0.

制約は次のとおりです:

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

これは、解いてみるまでは、一見するとそれほど難しくないと思われる問題の 1 つだと思います。

まず、最も単純な洞察から始めましょう。文字は、それ自体 (1 つの文字として) または 2 桁の数字の一部としてデコードできます。
最初のオプションの場合、0 自体は何にもマッピングされないため、1 から 9 までの数字のみを使用できます。
ただし、2 桁の数字は 10 から 26 までです。

この章の前の問題と同様に、文字列を反復処理するときに各文字までデコードする方法の数を保持する dp 配列を作成することから始めます。
Climbing Stairs と非常に似ていますが、まだ何もデコードしていないという事実を考慮する必要があるため、配列を長さ s.length 1 で初期化する必要があります。
言い換えれば、文字がない場合、「デコード」する方法は 1 つだけです。まったくデコードしないのです。

したがって、1 になる最初のインデックスを除いて、すべての値を 0 として初期化できます。

let dp = Array.from({ length: s.length   1 }, () => 0);

dp[0] = 1;

ここでも、前の問題と同様に、下位 2 つの値を保持する必要があるため、文字列の最初の文字をデコードする方法の数に対応する配列の 2 番目のスロットを初期化する必要があります。

「0」の場合はデコードできないことがわかっているため、この場合、デコードする方法の数は 0 になります。
デコードできないは、デコードをまったく実行しないとは異なることに注意してください。最初のケースでは、デコードする方法の数は0ですが、2番目のケースでは( dp[0] を使用しただけです)、デコードする方法の数は 1.

他のすべての場合、それは単一の文字であるため、デコードする方法は 1 つ だけです。したがって、それに応じて dp[1] を初期化します:

dp[1] = (s[0] === '0') ? 0 : 1;

これで、3 番目のインデックスから反復を開始できます。前の 1 桁と前の 2 桁を同時に調べます。

前の数字が数値 0 でない限り、配列の前のスロットにあるものは何でも追加できます。

そして、前の 2 桁が 10 から 26 までの数値を構成している限り、対応する解も追加できます。全体的には次のようになります:

for (let i = 2; i 



注記
便利な単項プラス演算子を使用して、文字列文字を数値に変換しています。問題の制約から、文字列 s には数字のみが含まれていることがわかります。


この時点で、最後のインデックス (s.length に対応する) に結果が入っているので、それを返すだけです。


function numDecodings(s: string): number {
  /* ... */

  return dp[s.length]; 
}




全体的に、私たちのソリューションは次のようになります:


function numDecodings(s: string): number {
  let dp = Array.from({ length: s.length   1 }, () => 0);

  dp[0] = 1;
  dp[1] = (s[0] === '0') ? 0 : 1;

  for (let i = 2; i 




  
  
  時間と空間の複雑さ


このソリューションの時間と空間の複雑さは両方とも $O(n)$の上）

 定数操作を行うすべての文字を反復処理するため、入力サイズが増加するにつれてサイズも増加する配列を保持する必要があります。


次はコインチェンジという問題です。それまではコーディングを楽しんでください。