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

Note

We're converting the string characters to numbers with the handy unary plus operator. We know from the problem constraints that the string s only contains digits.

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 サイトの他の関連記事を参照してください。