LeetCode 瞑想: ワードブレイク

この問題の説明は次のとおりです:

文字列 s と文字列の辞書 wordDict が与えられた場合、s を 1 つ以上の辞書単語のスペースで区切られたシーケンスに分割できる場合は true を返します。

辞書内の同じ単語がセグメンテーションで複数回再利用される可能性があることに注意してください。

例:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true

Explanation: Return true because "leetcode" can be segmented as "leet code".

または:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true

Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

または:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

また、制約は

wordDict のすべての文字列が **一意である** こと、および次のことを示しています:

1 1 1 s と wordDict[i] は英小文字のみで構成されます。

---

動的プログラミング ソリューションを続けて、dp 配列を構築して、各インデックスの wordDict で s を単語に分割できるかどうかを追跡する、一般的なボトムアップ アプローチを見ていきます。

各インデックス

$私私$私 dp 配列内の は、文字列全体をインデックスで始まる単語に分割できるかどうかを示します。 $私私$私 .

最初は false の値で作成しましょう:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true

Explanation: Return true because "leetcode" can be segmented as "leet code".

最後のインデックスは空の文字列であり、壊れやすい、つまり有効であると見なすことができます:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true

Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

逆に、 s のインデックスごとに、そのインデックス以降の wordDict 内の単語に到達できるかどうかを確認できます。

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

まだ s の範囲内 (i word.length になります。

let dp = Array.from({ length: s.length + 1 }, () => false); // +1 for the base case, out of bounds

wordDict でそれを 任意の 単語に分割できれば、他の単語を探し続ける必要がないので、ループから抜け出すことができます。

dp[s.length] = true; // base case

最後に、dp[0] を返します。文字列全体が wordDict で単語に分解できる場合、その値には true が格納され、それ以外の場合は false が格納されます。

for (let i = s.length - 1; i >= 0; i--) {
  for (const word of wordDict) {
    /* ... */
  }
}

そして、最終的な解決策は次のとおりです:

for (let i = s.length - 1; i >= 0; i--) {
  for (const word of wordDict) {
    if (i + word.length <= s.length && s.slice(i, i + word.length) === word) {
      dp[i] = dp[i + word.length];
    }
    /* ... */
  }
}

時間と空間の複雑さ

時間計算量は次のとおりです。 $O(n\ast m\ast t)O(n\; *\; m\; *\; t)$O(n∗m∗t) どこ $nn$n は文字列 s、 $mm$m は wordDict 内の単語の数であり、 $tt$t は、wordDict 内の単語の最大長です。s 内の各文字に対して word.length を使用するスライス操作を使用して、wordDict 内の各単語を実行する入れ子になったループがあるためです。

空間の複雑さは

$O(n)O(n)$O(n) s のインデックスごとに dp 配列を保存するためです。

---

シリーズ最後の動的計画問題は、最長増加部分列です。それまで、コーディングを楽しんでください。

以上がLeetCode 瞑想: ワードブレイクの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。