Leetcode

leetcode139。ワードブレイク



Leetcode 139 Word Break



空でない文字列sと空でない単語のリストを含む辞書wordDictが与えられた場合、sを1つ以上の辞書単語のスペースで区切られたシーケンスにセグメント化できるかどうかを判別します。

注意：



辞書内の同じ単語は、セグメンテーションで複数回再利用できます。
辞書に重複する単語が含まれていないと思われるかもしれません。
例1：

入力：s =“ leetcode”、wordDict = [“ leet”、“ code”]
出力：true
説明：「leetcode」は「leetcode」としてセグメント化できるため、trueを返します。



文字列s、辞書を与え、s文字列を辞書内の単語に分割できるかどうかを尋ねます。
辞書にある単語は再利用できます。

考え：
最初にトップダウンのアイデアを考えます
s =“ leetcode”と仮定します
次のsplitメソッドがあります（タイトルでは、ここでコンマをクリアするためにスペース分割を使用します）：
l、eetcode
、etcode
読み取り、tcode
リート、コード
最後のletetcodまでのleetc、codeなど、e

左右に分割される部分文字列ごとに、上記の左右分割方法を再帰的に
あなたはleetcを見ることができます、あなたがコードで左のleetcを分割するとき、あなたはちょうど今l、le、lee、leetに遭遇するでしょう。
したがって、ハッシュを使用して、特定の部分文字列ごとに取り外し可能なフラグを保存する必要があります
このコードは実装されていません



dpのアイデアに戻す
dpを使用して、各インデックスiに対応する取り外し可能なフラグを保存し、左側の ''に対応するインデックス0を追加します。
dpアイデアリファレンスhttps://www.cnblogs.com/grandyang/p/4257740.html
の解決策2：
「dp [i]は、範囲[0、i）の部分文字列を分割できるかどうかを示します。処理したいので、dp配列の長さはs文字列の長さより1大きいことに注意してください。空の文字列の場合、dp [0]をtrueに初期化してから、トラバースを開始します。現時点では再帰関数がないため、ここでトラバースするには2つのforループが必要であることに注意してください。したがって、すべての部分文字列を反復処理する必要があります。jを使用して、範囲[0、i）の部分文字列を2つの部分に分割します。 0、j）および[j、i）、ここで範囲[0、j）はdp [j]、範囲[j、i）はs .substr（j、ij）、ここでdp [j]は以前の状態、計算済み、直接取得できます。辞書でs.substr（j、ij）が存在するかどうかを確認する必要があります。両方がTrueの場合、dp [i]をtrueに割り当て、中断します。この時点では、[0、i）の範囲を分割できるため、jを使用して[0、i）の範囲を分割する必要はありません。最後に、dp配列の最後の値は、配列全体を分割できるかどうかのブール値です。

C ++コード

bool wordBreak(string s, vector& wordDict) { unordered_set word_set(wordDict.begin(), wordDict.end()) vector dp(s.size() + 1, false) dp[0] = true for(int i = 0 i

Javaコード：

public boolean wordBreak(String s, List wordDict) { HashSet wordSet = new HashSet(wordDict) boolean[] dp = new boolean[s.length() + 1] dp[0] = true for (int i = 0 i