[LeetCode] 0091. デコード方法

Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリリンク

中くらい

からの手紙を含むメッセージ アリゾナ州 できる エンコードされた 次のマッピングを使用して数値に変換します。

「A」 -> 「1」 「B」 -> 「2」 ... 「Z」 -> 「26」

に デコードする エンコードされたメッセージの場合は、すべての数字をグループ化してから、上記のマッピングの逆を使用して文字にマッピングし直す必要があります (たとえば、複数の方法がある場合があります)。 "11106" 以下にマッピングできます。

「AAJF」 グループ分けで (1 1 10 6)
「KJF」 グループ分けで (11 10 6)

グループ化に注意してください (1 11 06) は無効です。 "06" にマッピングすることはできません 「ふ」 以来 "6" とは異なります "06".

文字列を与える s 数字のみを含む場合は返します の番号の方法の デコードする それ.

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

例 1:

入力： s = "12"
出力： 2
説明： 「12」は「AB」（1 2）または「L」（12）としてデコードできます。

例 2:

入力： s = "226"
出力： 3
説明： 「226」は、「BZ」（2 26）、「VF」（22 6）、または「BBF」（2 2 6）としてデコードできます。

例 3:

入力： s = "06"
出力： 0
説明： 「06」は先頭にゼロがあるため「F」にマッピングできません (「6」は「06」とは異なります)。

制約:

1 <= s.length <= 100
s 数字のみが含まれており、先頭にゼロが含まれる場合があります。

パイソン

				
					# 時間計算量: O(n) # 空間計算量: functools import lru_cache クラスからの O(n) 解決策: @lru_cache(None) def recursiveWithMemo(self, Index: int, s: str) -> int: ifindex == len (s): s[index] == '0'の場合は1を返します。index == len(s) - 1の場合は0を返します。answer = self.recursiveWithMemo(index + 1, s) if int(s[index] :index + 2]) <= 26: 答え += self.recursiveWithMemo(index + 2, s) 答えを返す def numDecodings(self, s: str) -> int: return self.recursiveWithMemo(0, s) s = " 12 インチ print(Solution().numDecodings(s))

中くらい

パイソン

関連記事