Word Break

+10

On vous donne une chaîne s et une liste de mots wordDict. Renvoyez true si vous pouvez découper s en morceaux de sorte que chaque morceau soit un mot de wordDict, et false sinon.

Les morceaux conservent leur ordre et utilisent ensemble chaque lettre de s exactement une fois. Un mot peut être utilisé autant de fois que vous le souhaitez, et vous n’êtes pas obligé d’utiliser tous les mots.

Fonction

wordBreak(s: string, wordDict: string-array) → boolean

sstring: la chaîne à découper en mots
wordDictstring-array: les mots que vous pouvez utiliser, autant de fois que vous le souhaitez
Renvoieboolean: vrai si s peut être découpé en mots du dictionnaire, faux sinon

Contraintes

1 ≤ s.length ≤ 300
1 ≤ wordDict.length ≤ 1000
1 ≤ wordDict[i].length ≤ 20
s et chaque mot ne contient que des lettres minuscules de l’alphabet anglais.
Les mots de wordDict sont tous différents.

Exemples

Entrée: s = "sunflowerseed"wordDict = ["sun", "flow", "flower", "seed"]
Sortie: true
Explication: Découpez-le en sun, flower, seed. Prendre flow après sun ne mène nulle part, car aucun mot ne commence par er, qui reste, donc le premier mot qui convient n’est pas toujours le bon.

Entrée: s = "bananaban"wordDict = ["ban", "ana"]
Sortie: true
Explication: ban + ana + ban couvre la chaîne et utilise ban deux fois, ce qui est autorisé.

Entrée: s = "pineappletart"wordDict = ["pine", "apple", "pineapple", "tar"]
Sortie: false
Explication: La chaîne commence par pine + apple ou par pineapple, et dans les deux cas, il reste tart. Le seul mot qui convient est tar, qui laisse un t isolé ; aucune coupure ne fonctionne donc.

+21 tests cachés à la soumission

Pour aller plus loin

Renvoie le plus petit nombre de mots qu’une coupe valide peut utiliser, ou -1 si s ne peut pas être découpé. Qu’est-ce qui change dans le tableau, et le temps d’exécution change-t-il ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

La découpe gloutonne échoue dans les deux sens : prendre d’abord le mot le plus court découpe sunflowerseed en sun + flow, et prendre d’abord le plus long découpe carpetal en carpet et laisse al de côté. Il faut donc essayer les différentes possibilités, et une chaîne peut être découpée d’un nombre exponentiel de façons. La clé, c’est que la possibilité de découper le reste de la chaîne dépend uniquement de l’endroit où ce reste commence ; il n’y a donc que n + 1 questions différentes. Ci-dessous, n est la longueur de s, m le nombre de mots et L la longueur du mot le plus long.

Essayez chaque mot à chaque position

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Lisez s de gauche à droite. Quel que soit le premier morceau, il doit s’agir d’un mot par lequel s commence. Essayez chacun de ces mots et, pour chacun, posez la même question au sujet des lettres restantes. Si un mot quelconque permet de découper entièrement la chaîne, la réponse est true. Sinon, c’est false. Lorsqu’il ne reste plus rien, vous avez découpé toutes les lettres : c’est donc une réussite.

Cette méthode essaie tous les premiers mots possibles, puis tous les deuxièmes mots possibles, et ainsi de suite. Elle ne peut donc manquer aucun découpage valide, et chaque true qu’elle renvoie correspond à un véritable découpage.

Elle est lente, car elle vérifie plusieurs fois les mêmes chaînes restantes. Prenez 299 copies de a, suivies d’un b, avec les mots a, aa et ainsi de suite jusqu’à dix a. Chaque façon de découper les a en blocs de dix au maximum atteint le b et échoue à cet endroit, et il existe plus de 10^89 façons de le faire. La récursion doit toutes les essayer avant de pouvoir répondre false.

Algorithme

Écrivez une fonction auxiliaire canSplit(start) qui indique si les lettres de l’index start jusqu’à la fin peuvent être découpées en mots.
Si start est égal à la longueur de s, renvoyez true.
Pour chaque mot, vérifiez si s le contient à partir de l’index start.
Si c’est le cas et que canSplit(start + length of the word) vaut true, renvoyez true.
Si aucun mot ne convient, renvoyez false. La réponse est canSplit(0).

def wordBreak(s, wordDict):
    def can_split(start):
        # Can s[start:] be cut into dictionary words?
        if start == len(s):
            return True  # nothing left to cut
        for word in wordDict:
            if s.startswith(word, start) and can_split(start + len(word)):
                return True
        return False

    return can_split(0)

Récursion avec mémoïsation

Intuition

La réponse pour un reste ne dépend que de son point de départ, et start ne prend que n + 1 valeurs. Dans l’exemple avec les a, le reste qui commence à l’index 20 est atteint après deux blocs de dix, après vingt a seuls et de très nombreuses autres façons, et sa réponse est false à chaque fois. Enregistre la réponse pour chaque point de départ la première fois que tu la calcules, puis relis-la par la suite.

Un emplacement de mémo nécessite trois états : pas encore calculé, true et false. Les réponses false sont celles qui comptent. Une réponse true met immédiatement fin à toute la recherche ; ainsi, le travail répété par la récursion simple se trouve entièrement dans les branches qui échouent.

Chaque point de départ est calculé une seule fois et essaie chaque mot, en comparant jusqu’à L lettres, donc le temps est de O(n × m × L) : au maximum 300 × 1000 × 20 = 6 × 10^6 vérifications de lettres ici. Le mémo et la pile d’appels utilisent un espace de O(n), et les appels s’imbriquent jusqu’à 300 niveaux.

Algorithme

Crée un mémo avec un emplacement par index, chacun marqué comme non calculé.
Dans canSplit(start), renvoie true à la fin de la chaîne, et renvoie la réponse enregistrée si l’emplacement pour start en contient une.
Sinon, essaie chaque mot qui commence à start, comme dans la récursion simple, et arrête-toi au premier dont le reste peut être découpé.
Enregistre le résultat dans l’emplacement, y compris false, et renvoie-le.
Renvoie canSplit(0).

def wordBreak(s, wordDict):
    memo = [None] * len(s)  # memo[start]: answer for s[start:], None until worked out

    def can_split(start):
        if start == len(s):
            return True
        if memo[start] is not None:
            return memo[start]
        result = False
        for word in wordDict:
            if s.startswith(word, start) and can_split(start + len(word)):
                result = True
                break
        memo[start] = result
        return result

    return can_split(0)

De bas en haut sur les préfixes avec un ensemble de hachage

Intuition

Changeons de perspective et travaillons sur les préfixes. Soit canEnd[i] qui indique si les i premières lettres peuvent être découpées en mots. Le préfixe vide n’a besoin d’aucun mot, donc canEnd[0] vaut true. Les end premières lettres peuvent être découpées exactement lorsque leur dernier morceau, les lettres de start à end, est un mot et que les lettres qui le précèdent peuvent être découpées, c’est-à-dire que canEnd[start] vaut true. Remplis le tableau de gauche à droite et chaque canEnd[start] dont tu as besoin est déjà connu.

Au lieu de comparer les m mots à chaque position, place les mots dans un ensemble de hachage et recherche les derniers morceaux possibles. Aucun mot ne dépasse L lettres, donc seuls les L morceaux qui se terminent à end peuvent correspondre. Pour sunflowerseed, canEnd devient vrai en 0, en 3 (sun), en 7 (flow), en 9 (flower) et en 13 (seed après la position 9), donc la réponse est true. La position 7 ne mène nulle part, car aucun mot ne commence par er, et le tableau n’en tient pas compte.

Il y a n positions, chacune recherche au plus L morceaux, et construire et hacher un morceau coûte jusqu’à L étapes. Cela représente O(n × L²), soit au maximum 300 × 20 × 20 = 1.2 × 10^5 étapes de lecture de lettres, quelle que soit la taille du dictionnaire. La construction de l’ensemble parcourt chaque mot une fois, soit O(m × L), donc le coût total est O(m × L + n × L²). L’ensemble contient les mots, soit O(m × L) lettres, et le tableau contient n + 1 indicateurs. Il n’y a pas de récursivité.

Algorithme

Place chaque mot dans un ensemble de hachage et note la longueur L du mot le plus long.
Crée canEnd avec n + 1 entrées, toutes à false, et définis canEnd[0] à true.
Pour chaque end de 1 à n, essaie chaque length de 1 à min(L, end).
Si canEnd[end-length] vaut true et que le morceau de cette longueur se terminant à end se trouve dans l’ensemble, définis canEnd[end] à true et arrête d’essayer les longueurs.
Retourne canEnd[n].

def wordBreak(s, wordDict):
    words = set(wordDict)
    longest = max(len(word) for word in wordDict)
    n = len(s)
    # can_end[i]: the first i letters split into dictionary words
    can_end = [False] * (n + 1)
    can_end[0] = True  # the empty prefix needs no words
    for end in range(1, n + 1):
        # The last word is s[end-length:end], and no word is longer than longest.
        for length in range(1, min(longest, end) + 1):
            if can_end[end - length] and s[end - length:end] in words:
                can_end[end] = True
                break
    return can_end[n]

Pièges et cas limites

La plupart des mauvaises réponses viennent du fait de s’engager trop tôt dans une seule découpe, ou d’effectuer une recherche qui ne mémorise jamais ses échecs.

Découper de manière gloutonne. Prendre d’abord le mot le plus long découpe carpetal en carpet et laisse al, alors que car + petal fonctionne. Prendre d’abord le mot le plus court échoue avec sunflowerseed.
Vérifier uniquement que chaque lettre de s apparaît dans au moins un mot. Avec les mots aaaa et aa, chaque morceau a une longueur paire, donc aaaaaaa, qui compte sept lettres, ne peut pas être découpé.
Ne stocker que les réponses true dans le mémo. Un résultat true met de toute façon fin à la recherche. Les répétitions de calcul se produisent dans les branches false ; un mémo qui ne les contient pas reste donc exponentiel.
Créer un tableau avec une entrée en moins. canEnd[i] concerne les i premières lettres, et 0 comme n sont des valeurs valides ; il faut donc n + 1 entrées.
Comparer au-delà de la fin de s lorsqu’un mot est plus long que ce qu’il reste, par exemple le mot abc avec ab. Vérifiez les longueurs avant de comparer les lettres.
En Lua et R, les positions des chaînes commencent à 1 : un morceau de longueur k qui se termine à la lettre e commence à la lettre e-k+1.

Questions fréquentes4

Quelle est la complexité temporelle de Word Break ?

La table ascendante avec un ensemble de hachage s’exécute en O(m × L + n × L²) temps, où n est la longueur de s, m le nombre de mots et L le mot le plus long. La construction de l’ensemble lit chaque mot une fois, et chacune des n positions recherche au plus L morceaux de jusqu’à L lettres. Si vous comparez chaque mot à chaque position à la place, la complexité est O(n × m × L). La récursion simple sans mémoïsation est exponentielle.

Pourquoi une approche gloutonne échoue-t-elle pour le problème Word Break ?

Une règle gloutonne s’engage sur un mot et ne le réexamine jamais. La stratégie du plus long d’abord découpe carpetal en carpet et al, tandis que car + petal fonctionne. La stratégie du plus court d’abord découpe sunflowerseed en sun + flow et se retrouve bloquée sur erseed. La programmation dynamique conserve chaque position qu’une découpe peut atteindre, et ne perd donc jamais la bonne.

Word Break est-il un problème de programmation dynamique ou un problème de graphe ?

Les deux points de vue fonctionnent. En programmation dynamique, canEnd[i] indique si les i premières lettres peuvent être découpées, à partir de préfixes plus petits. En tant que graphe, chaque indice est un nœud, avec une arête de i à j lorsque les lettres de i à j forment un mot, et on cherche à savoir si le nœud n est accessible depuis le nœud 0. Une recherche en largeur avec un ensemble des nœuds visités effectue le même travail que le tableau.

Comment lister chaque phrase au lieu de renvoyer true ou false ?

Utilisez le retour sur trace : à chaque index, essayez chaque mot qui convient et appelez récursivement l’algorithme sur le reste, en construisant la phrase au fur et à mesure. Mémorisez la liste des phrases pour chaque index afin qu’un reste ne soit résolu qu’une seule fois. Commencez par exécuter le tableau de valeurs vrai ou faux afin qu’une chaîne qui ne peut pas être découpée passe directement la recherche. Le nombre de phrases peut croître de façon exponentielle ; la taille de la sortie détermine donc le temps d’exécution.

Python

def wordBreak(s, wordDict):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

s = "sunflowerseed"
wordDict = ["sun", "flow", "flower", "seed"]

Attendu

true

Word Break

Fonction

Contraintes

Exemples

Indices

Solution

Essayez chaque mot à chaque position

Récursion avec mémoïsation

De bas en haut sur les préfixes avec un ensemble de hachage

Pièges et cas limites

Questions fréquentes4

Problèmes similaires