Décomposition de mots
Leçon 14 sur 14 du cours Tries - Série Structures de données n°8 de Coddy.
Étant donné une chaîne s et un dictionnaire de mots, pouvons-nous découper s en une séquence de mots du dictionnaire sans qu'il ne reste rien ? "leetcode" se décompose en "leet" + "code" si les deux sont dans le dictionnaire ; "catsandog" ne se décompose pas, peu importe la façon dont nous le coupons.
Une approche par programmation dynamique permet de résoudre le problème. Définissez dp[i] comme les i premiers caractères peuvent-ils être segmentés ? Commencez avec dp[0] = true. Pour chaque i où dp[i] est vrai, parcourez le trie à partir de la position i dans la chaîne ; chaque fois que le parcours arrive sur un nœud isEndOfWord à l'index j, définissez dp[j+1] = true.
Le trie rend chaque parcours rapide : un seul caractère manquant y met fin. La réponse finale se trouve dans dp[n].
Défi
MoyenÉcrivez une fonction wordBreak qui reçoit une chaîne de caractères s et un tableau de chaînes dictionary, et renvoie true si s peut être segmentée en un ou plusieurs morceaux sans espaces qui sont tous présents dans le dictionnaire, ou false sinon.
Une chaîne s vide est toujours segmentable.
Vous devez utiliser la classe Trie (fournie dans trie avec trienode) - n'utilisez pas les structures intégrées du langage comme les ensembles (sets), les dictionnaires (dicts) ou les maps pour compter ou suivre les éléments.
Essayez vous-même
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char s[4096], dLine[4096];
if (!fgets(s, sizeof(s), stdin)) s[0] = 0;
if (!fgets(dLine, sizeof(dLine), stdin)) dLine[0] = 0;
s[strcspn(s, "\r\n")] = '\0';
dLine[strcspn(dLine, "\r\n")] = '\0';
char* d[1024]; int dn = 0;
char* tok = strtok(dLine, " \t");
while (tok && dn < 1024) { d[dn++] = tok; tok = strtok(NULL, " \t"); }
printf("%s\n", wordBreak(s, d, dn) ? "true" : "false");
return 0;
}
Toutes les leçons de Tries - Série Structures de données n°8
3Défis d'entraînement
Plus long préfixe communCompter les mots avec un préfixeAutocomplétionPlus long mot du dictionnaireDécomposition de mots