Méditations LeetCode : coupure de mots

La description de ce problème est :

Étant donné une chaîne s et un dictionnaire de chaînes wordDict, renvoie true si s peut être segmenté en une séquence séparée par des espaces d'un ou plusieurs mots du dictionnaire.

Notez qu'un même mot du dictionnaire peut être réutilisé plusieurs fois dans la segmentation.

Par exemple :

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

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

Ou :

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.

Ou :

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

De plus, nos contraintes indiquent que toutes les chaînes de wordDict sont **uniques**, et :

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s et wordDict[i] sont constitués uniquement de lettres anglaises minuscules.

---

En continuant avec les solutions de programmation dynamique, nous pouvons examiner une approche ascendante populaire dans laquelle nous construisons un tableau dp pour savoir s'il est possible de diviser s en mots dans wordDict à chaque index.

Chaque indice $i$i dans le tableau dp indiquera s'il est possible de diviser la chaîne entière en mots commençant à l'index $i$i .

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.

Créons-le avec des valeurs initialement fausses :

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

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

Le dernier index est la chaîne vide, qui peut être considérée comme cassable, ou en d'autres termes, valide :

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.

En revenant en arrière, pour chaque index de s, nous pouvons vérifier si un mot de wordDict peut être atteint à partir de cet index :

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

Si nous sommes toujours dans les limites de s (i word.length <= s.length) et que nous trouvons le mot (s.slice(i, i word.length) === word), nous allons marquez cet emplacement comme la valeur de vérité de la "position suivante" dans laquelle nous pouvons casser la chaîne, qui sera i word.length :

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




<p>Si nous pouvons le diviser en <em>n'importe quel</em> mot dans wordDict, nous n'avons pas besoin de continuer à regarder d'autres mots, nous pouvons donc simplement sortir de la boucle :<br>
</p>

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

Enfin, nous renvoyons dp[0] — si la chaîne entière est décomposable en mots dans wordDict, sa valeur stockera vrai, sinon faux :

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

Et voici la solution finale :

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

Complexité temporelle et spatiale

La complexité temporelle est $O(n\ast m\ast t)$O(n∗m∗t) où $n$n est la chaîne s, $m$m est le nombre de mots dans wordDict, et $t$t est le mot de longueur maximale dans wordDict - car nous avons une boucle imbriquée qui parcourt chaque mot dans wordDict avec une opération de tranche qui utilise word.length pour chaque caractère de s.

La complexité de l'espace est $O(n)$O(n) à cause du tableau dp que nous stockons pour chaque index de s.

---

Le dernier problème de programmation dynamique de la série sera la sous-séquence croissante la plus longue. En attendant, bon codage.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!