LeetCode-Meditationen: Wortbruch

Die Beschreibung für dieses Problem lautet:

Bei einer gegebenen Zeichenfolge s und einem Wörterbuch mit Zeichenfolgen wordDict wird „true“ zurückgegeben, wenn s in eine durch Leerzeichen getrennte Folge von einem oder mehreren Wörterbuchwörtern segmentiert werden kann.

Beachten Sie, dass dasselbe Wort im Wörterbuch in der Segmentierung mehrmals wiederverwendet werden kann.

Zum Beispiel:

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

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

Oder:

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.

Oder:

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

Außerdem weisen unsere Einschränkungen darauf hin, dass alle Zeichenfolgen von wordDict **einzigartig** sind und:

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s und wordDict[i] bestehen nur aus englischen Kleinbuchstaben.

---

Um mit dynamischen Programmierlösungen fortzufahren, können wir uns einen beliebten Bottom-up-Ansatz ansehen, bei dem wir ein dp-Array erstellen, um zu verfolgen, ob es möglich ist, s in WordDict an jedem Index in Wörter aufzuteilen.

Jeder Index $\mathrm{ich}$ich im dp-Array gibt an, ob es möglich ist, die gesamte Zeichenfolge beginnend beim Index in Wörter aufzuteilen $\mathrm{ich}$ich .

Note

dp needs to be of size s.length 1 to hold the edge case of an empty string, in other words, when we're out of bounds.

Lassen Sie es uns mit anfänglich falschen Werten erstellen:

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

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

Der letzte Index ist die leere Zeichenfolge, die als zerbrechlich oder mit anderen Worten als gültig betrachtet werden kann:

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.

Rückwärts gehend können wir für jeden Index von s prüfen, ob ab diesem Index ein beliebiges Wort in wordDict erreichbar ist:

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

Wenn wir uns immer noch innerhalb der Grenzen von s (i word.length <= s.length) befinden und das Wort (s.slice(i, i word.length) === Wort) finden, werden wir es tun Markieren Sie diesen Slot als Wahrheitswert der „nächsten Position“, an der wir die Zeichenfolge unterbrechen können. Dies ist i word.length:

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




<p>Wenn wir es in <em>jedes</em> Wort in WordDict aufteilen können, müssen wir nicht ständig nach anderen Wörtern suchen, sondern können einfach aus der Schleife ausbrechen:<br>
</p>

<pre class="brush:php;toolbar:false">dp[s.length] = true; // base case

Schließlich geben wir dp[0] zurück – wenn die gesamte Zeichenfolge in wordDict in Wörter zerlegbar ist, speichert ihr Wert true, andernfalls false:

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

Und hier ist die endgültige Lösung:

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];
    }
    /* ... */
  }
}

Zeit- und Raumkomplexität

Die zeitliche Komplexität ist $O(n\ast m\ast t)$O(n∗m∗t) Wo $n$n ist die Zeichenfolge s, $m$m ist die Anzahl der Wörter in wordDict und $t$t ist das Wort mit der maximalen Länge in WordDict – da wir eine verschachtelte Schleife haben, die jedes Wort in WordDict mit einer Slice-Operation durchläuft, die word.length für jedes Zeichen in s verwendet.

Die räumliche Komplexität ist $O(n)$O(n) aufgrund des dp-Arrays, das wir für jeden Index von s speichern.

---

Das letzte dynamische Programmierproblem in der Reihe wird die längste ansteigende Teilsequenz sein. Bis dahin viel Spaß beim Codieren.

Das obige ist der detaillierte Inhalt vonLeetCode-Meditationen: Wortbruch. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!