Word Break II 問題解決チュートリアル:3つのソリューションの完全比較 | LeetCode 140 ベストプラクティス

Word Break II 問題解決チュートリアル図 | LeetCode 140

この記事では、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 <= 20
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 10
  • s そして 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))
				
			

単語ブレイクII 問題解決戦略

この問題では、実行可能性を判断するだけでなく、考えられるすべてのカットを出力する必要があるため、バックトラッキングが必要です。しかし、純粋なバックトラッキングでは、「最終的に解のないカットが多数存在する」テストケースではタイムアウトしてしまいます。重要な最適化はメモ化です。ハッシュテーブルを使用して「インデックス i から開始して形成できる文」を記録し、同じ開始点に対して一度だけ計算を行い、その結果を直接再利用します。

単語分割IIアルゴリズムの手順

  1. 辞書をセットに追加し、メモ化されたハッシュテーブルのメモを作成します(キーは開始インデックスです)。
  2. dfs(start)を定義します。startがnと等しい場合、空の文字列のみを含む配列を返します。
  3. メモに既に書き始めがある場合は、そのまま返送してください。
  4. 末尾(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)この記事では