LeetCode 瞑想: 解読方法

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

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

「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 文字であるため、デコードする方法は 1 つ だけです。したがって、それに応じて dp[1] を初期化します。

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

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

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

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

for (let i = 2; i <= s.length; i++) {
  const prevDigit = s[i - 1];
  const twoPrevDigits = s.slice(i - 2, i);
  if (+prevDigit !== 0) {
    dp[i] += dp[i - 1];
  }

  if (10 <= +twoPrevDigits && +twoPrevDigits <= 26) {
    dp[i] += dp[i - 2];
  }
}

At this point, we have the result in the last index (which corresponds to s.length) so we can just return it:

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

  return dp[s.length]; 
}

Overall, this is how our solution looks like:

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 <= s.length; i++) {
    const prevDigit = s[i - 1];
    const twoPrevDigits = s.slice(i - 2, i);
    if (+prevDigit !== 0) {
      dp[i] += dp[i - 1];
    }

    if (10 <= +twoPrevDigits && +twoPrevDigits <= 26) {
      dp[i] += dp[i - 2];
    }
  }

  return dp[s.length];
}

Time and space complexity

Both the time and space complexity for this solution are $O(n)$O(n) as we iterate through all the characters doing a constant operation, and we have to keep an array whose size will grow as our input size increases.

Next up is the problem called Coin Change. Until then, happy coding.

以上がLeetCode 瞑想: 解読方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。