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
• 1
• 1
• 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

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

Wenn wir es in jedes 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:

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 



<h4>
  
  
  Zeit- und Raumkomplexität
</h4>

<p>Die zeitliche Komplexität ist 

  <span><span><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo>∗</mo><mi>m</mi><mo>∗</mo><mi>t</mi><mo stretchy="false">)</mo></mrow>O(n * m * t) </semantics></math><span><span>O(n∗</span><span>m∗</span><span>t)</span></span></span>
</span>
 Wo 

  <span><span><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow>n </semantics></math><span><span>n</span></span></span>
</span>
 ist die Zeichenfolge s, 

  <span><span><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>m</mi></mrow>m </semantics></math><span><span>m</span></span></span>
</span>
 ist die Anzahl der Wörter in wordDict und 

  <span><span><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>t</mi></mrow>t </semantics></math><span><span>t</span></span></span>
</span>
 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.</p>

<p>Die räumliche Komplexität ist 

  <span><span><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow>O(n) </semantics></math><span><span>O(n)</span></span></span>
</span>
 aufgrund des dp-Arrays, das wir für jeden Index von s speichern.</p>


<hr>

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


          

            
  

            
        

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