Word Break

Q: Word Break est-il un problème de programmation dynamique ou de graphes ?

Les deux. En programmation dynamique, canEnd[i] indique si les i premières lettres peuvent être découpées. Dans un graphe, chaque indice est un nœud, avec une arête de i à j lorsque les lettres entre les deux forment un mot, et l’on cherche à savoir si n est accessible depuis 0. Un parcours en largeur effectue le même travail que le tableau.

MoyenProgrammation dynamique Hachage

+10

Vous obtenez une chaîne s et une liste de mots wordDict. Renvoyez true si vous pouvez découper s en morceaux qui sont tous des mots 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 tu peux utiliser, autant de fois que tu le souhaites
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 anglaises minuscules.
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 laisse er, par lequel aucun mot ne commence, 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: Aussi bien pine + apple que pineapple laissent tart. Seul tar convient à cet endroit, ce qui laisse un t isolé, donc aucune coupure ne fonctionne.

Pour aller plus loin

Retourne le plus petit nombre de mots qu’un découpage 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

S’engager sur un seul mot à la fois ne fonctionne pas, et essayer chaque découpage a une complexité exponentielle. Mais la possibilité de découper le reste de s dépend uniquement de son point de départ ; il n’y a donc que n + 1 questions. 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

Le premier morceau doit être un mot par lequel commence s. Essaie chaque mot de ce type et pose la même question pour les lettres restantes ; un reste vide signifie que toutes les lettres sont découpées. Essayer chaque premier mot, puis chaque deuxième mot, ne peut faire manquer aucun découpage valide.

Il vérifie encore et encore les mêmes restes. Avec 299 copies de a suivies d’un seul b, et les mots a, aa jusqu’à dix a, plus de 10^89 façons de découper les a en blocs atteignent le b et échouent, et la récursion les essaie toutes.

Algorithme

Écrivez canSplit(start) : les lettres de start jusqu’à la fin peuvent-elles être découpées ? Si start est égal à la longueur de s, renvoyez true.
Pour chaque mot que s contient à l’index start, si canSplit(start + its length) vaut true, renvoyez true.
Sinon, 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 une mémoïsation

Intuition

La réponse pour un reste dépend uniquement de start, qui prend n + 1 valeurs. Dans l’exemple avec les a, le reste à l’indice 20 est atteint après deux blocs de dix, après vingt a isolés et d’innombrables autres façons, et vaut false à chaque fois. Stocke une seule fois la réponse pour chaque valeur de start, puis réutilise-la.

La mémorisation doit conserver les réponses false. Une réponse true met immédiatement fin à toute la recherche ; tout le travail répété se trouve donc dans les branches qui échouent.

Chaque valeur de départ essaie chaque mot, en comparant jusqu’à L lettres : temps O(n × m × L), au plus 6 × 10^6 vérifications de lettres et espace O(n).

Algorithme

Créez un mémo avec un emplacement par index, chacun marqué comme non calculé.
Dans canSplit(start), renvoyez true à la fin de s, ou la réponse enregistrée si l’emplacement en contient une.
Sinon, essayez chaque mot comme dans la récursion simple, enregistrez le résultat dans l’emplacement, y compris false, puis renvoyez-le.

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

Travaillez sur les préfixes. canEnd[i] indique si les i premières lettres peuvent être découpées ; canEnd[0] vaut true, puisque le préfixe vide n’a besoin d’aucun mot. Les end premières lettres peuvent être découpées exactement lorsque leur dernière partie, de start à end, est un mot et que canEnd[start] vaut true. En remplissant le tableau de gauche à droite, chaque canEnd[start] dont vous avez besoin est déjà connu.

Placez les mots dans un ensemble de hachage. Aucun mot ne dépasse L lettres, donc seules les L parties se terminant à end peuvent correspondre, quelle que soit la taille du dictionnaire. Pour sunflowerseed, canEnd vaut true aux positions 0, 3, 7, 9 et 13 ; l’impasse en 7 ne pose pas de problème.

Pour chacune des n positions, on recherche au plus L parties, chacune nécessitant jusqu’à L étapes pour être construite et hachée : O(n × L²), soit au plus 1.2 × 10^5 étapes, auxquelles s’ajoute O(m × L) pour l’ensemble.

Algorithme

Placez les mots dans un ensemble de hachage ; notez la longueur maximale L.
Créez canEnd avec n + 1 entrées, toutes à false, et définissez canEnd[0] sur true.
Pour chaque end de 1 à n et chaque length de 1 à min(L, end) : si canEnd[end-length] vaut true et que le segment de cette longueur se terminant à end est dans l’ensemble, définissez canEnd[end] sur true et arrêtez.
Renvoyez 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

Découper de manière gloutonne. En prenant d’abord le plus long, carpetal est découpé en carpet, laissant al sans correspondance, alors que car + petal fonctionne ; en prenant d’abord le plus court, on se retrouve bloqué sur sunflowerseed.
Ne stocker que les réponses true dans le mémo. Le travail répété se trouve dans les branches false, donc l’exemple avec les a reste exponentiel.
Créer une table avec une entrée de moins. canEnd a besoin de n + 1 entrées, pour les longueurs de préfixe de 0 à n.
Comparer au-delà de la fin de s, par exemple le mot abc avec le reste ab. Vérifiez d’abord les longueurs.
En Lua et en R, les positions des chaînes commencent à 1 : un morceau de longueur k se terminant à la lettre e commence à e-k+1.

Questions fréquentes3

Quelle est la complexité temporelle de Word Break ?

Le tableau ascendant avec un ensemble de hachage s’exécute en O(m × L + n × L²), où n est la longueur de s, m le nombre de mots et L le mot le plus long. Comparer chaque mot à chaque position coûte O(n × m × L). La récursion simple a une complexité exponentielle.

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

Les deux. En programmation dynamique, canEnd[i] indique si les i premières lettres peuvent être découpées. Dans un graphe, chaque indice est un nœud, avec une arête de i à j lorsque les lettres entre les deux forment un mot, et l’on cherche à savoir si n est accessible depuis 0. Un parcours en largeur effectue le même travail que le tableau.

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

Retour arrière : à chaque indice, essaie chaque mot qui convient, applique récursivement la méthode au reste et mémorise la liste des phrases pour chaque indice. Exécute d’abord le tableau de valeurs vrai ou faux, afin qu’une chaîne qui ne peut pas être découpée évite la recherche. Le nombre de phrases peut croître de façon exponentielle, donc la taille de la sortie détermine le temps d’exécution.

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

Test #1

Test #2

Test #3

Arguments

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

Résultat attendu

true

Word Break

Fonction

Contraintes

Exemples

Indices

Solution

Essayez chaque mot à chaque position

Récursion avec une mémoïsation

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

Pièges et cas limites

Questions fréquentes3

Problèmes similaires