この記事では、LeetCode 140 Word Break II の解法を、問題解決のアプローチやアルゴリズムの手順から時間計算量や空間計算量まで、完全に解説します。また、境界ケースをまとめ、3 つの解法を比較することで、Word Break II を一度に理解できるようにしています。
Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリ リンク
文字列を与える s そして文字列の辞書 単語辞書、スペースを追加します s 各単語が有効な辞書単語である文を構築するには、そのような考えられるすべての文を返します。 任意の注文.
注記 辞書内の同じ単語がセグメンテーションで複数回再利用される可能性があること。
例 1:
入力: s = "猫と犬", wordDict = ["猫","猫","そして","砂","犬"] 出力: 【「猫と犬」「猫砂犬」】
例 2:
入力: s = "パイナップルペナップル", wordDict = ["アップル","ペン","アップルペン","パイン","パイナップル"] 出力: [「パインアップルペンアップル」、「パイナップルペンアップル」、「パインアップルペンアップル」] 説明: 辞書の単語を再利用できることに注意してください。
例 3:
入力: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] 出力: []
制約:
1 <= s.length <= 201 <= wordDict.length <= 10001 <= wordDict[i].length <= 10sそしてwordDict[i]小文字の英字のみで構成されています。- のすべての文字列
単語辞書は 個性的. - 入力は、回答の長さが 10 を超えないように生成されます。5.
パイソン
# 時間計算量: O(2^n) # 空間計算量: import List クラスの入力による O(2^n) 解決策: def wordBreak(self, s: str, wordDict: List[str]) -> List[str]: word_set = set(wordDict) memoization = {} return self._dfs(s, word_set, memoization) def _dfs(self, RemainingStr: str, wordSet: set, memoization: dict) -> List[str]: メモ化に残っているStrの場合: missingStr でない場合は、memoization[remainingStr] を返します。 range(1, len(remainingStr) + 1) 内の i の場合、[""] 結果 = [] を返します。wordSet 内の currentWord の場合、currentWord = RemainingStr[:i] を返します。 _dfs(remainingStr[i:], wordSet, memoization): results.append( currentWord + (" " if nextWord else "") + nextWord) memoization[remainingStr] = 結果は結果を返します s = "catsanddog" wordDict = ["cat" 、「猫」、「と」、「砂」、「犬」] print(Solution().wordBreak(s, wordDict))
LeetCode問題拡張演習
同じシリーズの他の問題解決ノートも練習用としてお勧めします。
さらに詳しく知りたい方はこちらをご覧ください
単語ブレイクII 問題解決戦略
この問題では、実行可能性を判断するだけでなく、考えられるすべてのカットを出力する必要があるため、バックトラッキングが必要です。しかし、純粋なバックトラッキングでは、「最終的に解のないカットが多数存在する」テストケースではタイムアウトしてしまいます。重要な最適化はメモ化です。ハッシュテーブルを使用して「インデックス i から開始して形成できる文」を記録し、同じ開始点に対して一度だけ計算を行い、その結果を直接再利用します。
単語分割IIアルゴリズムの手順
- 辞書をセットに追加し、メモ化されたハッシュテーブルのメモを作成します(キーは開始インデックスです)。
- dfs(start)を定義します。startがnと等しい場合、空の文字列のみを含む配列を返します。
- メモに既に書き始めがある場合は、そのまま返送してください。
- 末尾(end)を一覧表示します。s.slice(start, end)が辞書に含まれている場合は、dfs(end)を再帰的に呼び出し、各結果にプレフィックスを追加します。すべての結果を収集したら、それらをメモに格納し、返します。
単語分割II複雑性分析
| プロジェクト | 複雑 |
|---|---|
| 時間計算量 | O(n²·k + R) |
| 空間の複雑さ | O(n·R) |
Rは回答文の全長です。各開始インデックスは一度だけ完全に計算され、計算コストはO(n·k)です。開始点は全部でn個あります。最終的な部分文字列を組み立てるコストは出力サイズRと同程度です。メモ化テーブルにはすべての中間結果を格納する必要があり、必要なスペースはO(n·R)です。
境界ケースと単語分割におけるよくあるエラー II
- カットがない場合は、空の文字列を含む配列ではなく、空の配列を返します。
- メモ化されたキーは開始インデックスのみであり、事前に組み立てられたプレフィックスを含めることはできません。そうでない場合、再利用できません。
- 結果の数は非常に多く(指数関数的に)なる可能性があり、これはアルゴリズムの問題ではなく、問題自体の特性である。
- まず、Word Breakの動的計画法を用いて解が存在するかどうかを判断できます。解が存在しない場合は、時間の無駄を避けるため、解を直接返してください。
Word Break II の他のソリューションとの比較
| 解法 | 時間 | 空間 | 例示する |
|---|---|---|---|
| 純粋な後戻り | O(2^n) | の上) | 最悪の場合、データ計測が確実にタイムアウトしてしまうでしょう。 |
| まず実現可能性に関する動的計画法(DP)テストを実行し、それから逆算して検証する。 | O(n²·k + R) | の上) | 剪定は効果的であり、実際によく行われている。 |
| メモ化再帰 | O(n²·k + R) | O(n·R) | この記事では |
