Compte tenu d'un dictionnaire de mots et d'un personnage initial. Trouvez le mot le plus long possible dans le dictionnaire en ajoutant successivement un personnage au mot. À une instance donnée, le mot devrait être un mot valide dans le dictionnaire.
EX: A -> AT -> CAT -> Panier -> Graphique ....
3 Réponses :
L'approche de la force brute serait d'essayer d'ajouter des lettres à chaque index disponible à l'aide d'une première recherche de profondeur.
Donc, à partir de 'A', il y a deux endroits où vous pouvez ajouter une nouvelle lettre. Devant ou derrière le 'a', représenté par des points ci-dessous. P>
Si vous ajoutez un 't', il y a maintenant trois Positions. P> Vous pouvez essayer d'ajouter les 26 lettres à chaque position disponible. Le dictionnaire dans ce cas peut être une simple hashtable. Si vous ajoutez un 'Z' au milieu, vous obtenez «Azt» qui ne serait pas dans la casse-nutable, vous ne continuez donc pas de continuer sur cette voie dans la recherche. P> edit forte >: Le graphique de Nick Johnson m'a rendu curieux à quoi ressemblerait un graphique de tous les chemins maximaux. C'est une image grande (1,6 Mo) ici: p> http: // www.michaelfogleman.com/static/images/word_graph.png P> Modifier strong>: Voici une implémentation de python. L'approche brute-force fonctionne réellement dans une durée raisonnable (quelques secondes, en fonction de la lettre de départ). P> .A. Code> p> .at code> p> (10, ('a', 'ta', 'tap', 'tape', 'taped', 'tamped', 'stamped', 'stampede', 'stampedes', 'stampeders'))
(9, ('b', 'bo', 'bos', 'bods', 'bodes', 'bodies', 'boodies', 'bloodies', 'bloodiest'))
(1, ('c',))
(10, ('d', 'od', 'cod', 'coed', 'coped', 'comped', 'compted', 'competed', 'completed', 'complected'))
(10, ('e', 're', 'rue', 'ruse', 'ruses', 'rouses', 'arouses', 'carouses', 'carousels', 'carrousels'))
(9, ('f', 'fe', 'foe', 'fore', 'forge', 'forges', 'forgoes', 'forgoers', 'foregoers'))
(10, ('g', 'ag', 'tag', 'tang', 'stang', 'strang', 'strange', 'strangle', 'strangles', 'stranglers'))
(9, ('h', 'sh', 'she', 'shes', 'ashes', 'sashes', 'slashes', 'splashes', 'splashers'))
(11, ('i', 'pi', 'pin', 'ping', 'oping', 'coping', 'comping', 'compting', 'competing', 'completing', 'complecting'))
(7, ('j', 'jo', 'joy', 'joky', 'jokey', 'jockey', 'jockeys'))
(9, ('k', 'ki', 'kin', 'akin', 'takin', 'takins', 'takings', 'talkings', 'stalkings'))
(10, ('l', 'la', 'las', 'lass', 'lassi', 'lassis', 'lassies', 'glassies', 'glassines', 'glassiness'))
(10, ('m', 'ma', 'mas', 'mars', 'maras', 'madras', 'madrasa', 'madrassa', 'madrassas', 'madrassahs'))
(11, ('n', 'in', 'pin', 'ping', 'oping', 'coping', 'comping', 'compting', 'competing', 'completing', 'complecting'))
(10, ('o', 'os', 'ose', 'rose', 'rouse', 'rouses', 'arouses', 'carouses', 'carousels', 'carrousels'))
(11, ('p', 'pi', 'pin', 'ping', 'oping', 'coping', 'comping', 'compting', 'competing', 'completing', 'complecting'))
(3, ('q', 'qi', 'qis'))
(10, ('r', 're', 'rue', 'ruse', 'ruses', 'rouses', 'arouses', 'carouses', 'carousels', 'carrousels'))
(10, ('s', 'us', 'use', 'uses', 'ruses', 'rouses', 'arouses', 'carouses', 'carousels', 'carrousels'))
(10, ('t', 'ti', 'tin', 'ting', 'sting', 'sating', 'stating', 'estating', 'restating', 'restarting'))
(10, ('u', 'us', 'use', 'uses', 'ruses', 'rouses', 'arouses', 'carouses', 'carousels', 'carrousels'))
(1, ('v',))
(9, ('w', 'we', 'wae', 'wake', 'wakes', 'wackes', 'wackest', 'wackiest', 'whackiest'))
(8, ('x', 'ax', 'max', 'maxi', 'maxim', 'maxima', 'maximal', 'maximals'))
(8, ('y', 'ye', 'tye', 'stye', 'styed', 'stayed', 'strayed', 'estrayed'))
(8, ('z', 'za', 'zoa', 'zona', 'zonae', 'zonate', 'zonated', 'ozonated'))
+1. Cool pour attaquer des problèmes comme celui-ci toujours avec la technique de la force brute. Quelle serait l'ordre de la solution ci-dessus
Belle solution! Pas le très efficace depuis que vous devez tester 26 ^ n Possibilités d'une solution de longueur N-1 - qui est de la manière moins que le nombre de mots de longueur < CODE> N Si le mot n'est pas très court - mais cela obtient définitivement le travail.
Quelqu'un m'a minusé sans commentaire. Un peu drôle en considérant que j'ai une solution de travail complète. Façon d'aller alors!
Ce n'est pas 26 ^ n. La plupart des "nœuds" intermédiaires dans l'arborescence de recherche échouent, éliminant considérablement l'espace de recherche. Si ce n'était pas le cas, cela ne fonctionnerait pas.
Je crois que la commande est O (n ^ m), où n est le nombre moyen d'enfants de l'arbre de recherche (probablement autour de 4 pour un dictionnaire anglais) et m est la longueur moyenne des mots du dictionnaire.
Je viens de vérifier avec mon programme. Selon la lettre de départ, il n'y a que 14 858 feuilles dans l'arbre de recherche en moyenne. Max 80,116 (pour la lettre 'A').
@Fogle: Mon erreur; il est seulement 26 * (n + 1) * n (n) pour niveau n , où n (n) est le nombre de mots qui Passez en longueur n . Toujours pas le plus efficace possible, mais certainement suffisant.
Graphique impressionnant. Je voudrais toujours voir le graphique avec juste l'ensemble minimal des nœuds d'extrémité, cependant. :)
Qu'entendez-vous par «jeu minimal de nœuds d'extrémité»?
Un nœud est un «nœud de fin» s'il n'a pas d'enfants. Étant donné que certains nœuds sont des nœuds d'extrémité pour plusieurs lettres, il doit y avoir une sélection d'un ensemble de nœuds d'extrémité de sorte que chaque lettre ait une nœud d'extrémité (longueur maximale), mais l'ensemble de tous les nœuds d'extrémité est le plus petit possible.
Ah, je vois. Cela semble difficile. Je vais devoir y penser plus.
Le lien vers l'image est mort.
Si vous voulez faire cela une fois, je ferais ce qui suit (généralisé au problème du commençant par un mot complet):
Prenez tout votre dictionnaire et jetez tout ce qui n'a plus de superset des personnages Dans votre mot cible (disons qu'il a une longueur Si vous voulez rendre cela rapidement pour rechercher, je construirais un suffixe-Tree- comme la structure de données . Grouper tous les mots par longueur. Pour chaque mot de longueur 2, placez chacun de ses deux caractères dans un ensemble «sous-mot» et ajoutez ce mot à chacun des ensembles «super mots» de caractères. Vous avez maintenant un lien entre tous les mots de longueur valides 2 et tous les caractères. Faites la même chose avec des mots de longueur 3 et des mots de longueur valides 2. Vous pouvez maintenant commencer n'importe où dans cette hiérarchie et faire une première recherche de largeur pour trouver la branche la plus profonde. éditer: la vitesse de cette solution dépendra grandement sur la structure de la langue, mais si nous décidons de tout construire à l'aide d'ensembles avec (le binon initial en mots d'un certain la longueur prendra du temps linéaire afin de pouvoir être négligé; la formule réelle pour l'exécution est compliquée car elle dépend de la distribution des longueurs de mots; pour le cas où vous le faites d'un seul mot, il est encore plus compliqué car cela dépend de l'attendu nombre de mots plus longs qui ont des sous-mots plus courts.) m ). Puis binez les mots restants par longueur. Pour chaque mot de longueur m + 1 , essayez de laisser tomber chaque lettre et voyez si cela donne votre mot souhaité. Sinon, jetez-le. Vérifiez ensuite chaque mot de longueur m + 2 contre le jeu de longueur valide m + 1 , qui ne peut pas être réduit. Continuez jusqu'à ce que vous trouviez un ensemble vide; La dernière chose que vous avez trouvée sera la plus longue.
log (n) performance pour toutes les opérations (c'est-à-dire que nous utilisons des arbres noirs rouges ou similaires) et nous avons n (m) mots de longueur m , puis pour former le lien entre les mots de longueur m + 1 et m sera approximativement (m + 1) * m * n (m + 1) * journal (n (m)) heure (en tenant compte de cette chaîne compare à la durée linéaire de la longueur de la chaîne). Puisque nous devons le faire pour toutes les longueurs de mots, le temps d'exécution de la construction de la structure de données complète sera quelque chose sur l'ordre de
En supposant que vous devez le faire à plusieurs reprises (ou que vous souhaitez la réponse pour chacune des 26 lettres), faites-le en arrière:
Puis, pour obtenir la chaîne pour un préfixe donné, commencez simplement avec ce préfixe et regardez-le à plusieurs reprises et ses extensions dans le dictionnaire.
Voici le code Python d'échantillon: et sa sortie pour chaque lettre de l'alphabet: EDIT: Compte tenu de la mesure dans laquelle les branches fusionnent vers la fin , Je pensais qu'il serait intéressant de dessiner un graphique pour démontrer ceci: Une extension intéressante de ce défi: il est probable qu'il existe plusieurs mots de plusieurs longueurs pour certaines lettres. Quel ensemble de chaînes minimise le nombre de nœuds finaux (par exemple, fusionne la plupart des lettres)? 
Joli. Environ 6-8 fois plus vite que le mien. Mais cela ne donne qu'un seul chemin pour chaque lettre de départ, tandis que la mine donne 380 000 chemins possibles (pour les 26 lettres combinées). En fin de compte, cela dépend de ce que l'OP aurait besoin de l'algorithme. (P.S. 'Abranchié' n'est pas dans mon dictionnaire!)
Plutôt vrai. Vous auriez pu générer tous les chemins, ou tout simplement tous les chemins max-longueur, en stockant une liste des extensions par rapport à chaque terme, au lieu de la plus longue trouvée jusqu'à présent. En ce qui concerne le dictionnaire, j'utilise simplement celui de l'USR / USR / dict / dict / mots sur OSX 10.5. :)
+1 pour l'idée graphique. Consultez ma réponse pour un graphique de tous les chemins maximaux. :)
Problème intéressant. Qu'avez-vous essayé jusqu'à présent et où êtes-vous coincé?
Définir "Dictionnaire des mots". Est-ce une table de hachage, une trie ou quoi? Si c'est une trie, une simple recherche de DF fonctionnera. Est-ce un arbre suffixe que vos tags suggèrent?
Cela ressemble à un problème de devoirs, mal spécifié.
Je crois que c'est en fait une question d'entrevue Amazon.
Je ne vois pas de problème avec cette question du tout.
@lvlad DF? Une caractéristique du dictionnaire vous donnerait si le mot est valide ou non (hypothèse de table de hachage). Je pensais que l'utilisation d'un suffixe ou de trie pour le dictionnaire aiderait à vérifier à chaque instance si le mot est valide ou non. La structure de données est flexible. @Michael j'ai pensé à le faire d'une manière inverse. Trier les mots du dictionnaire en fonction de la longueur. Prenez le mot le plus long, essayez de supprimer le caractère du mot et de continuer à vérifier s'il s'agit d'un mot valide ou non. Ceci est plus d'une méthode de force brute.
Si vous avez mis en cache les résultats, ce ne serait pas une mauvaise méthode du tout ...
Algoman, plus de contexte et vos propres réflexions sur le problème contribueraient à ce que cela se sente moins de "s'il vous plaît résoudre mon problème pour moi" Demande, et plus d'une question dirigée.
@ZIV Ouais. j'ai compris. Je suis très nouveau ici. Je vais essayer de m'expliquer beaucoup plus plus clair et posterai ma solution, ce que j'ai essayé jusqu'à présent.
Si c'est une question de devoirs, vous devriez lire ceci: meta.stackexchange.com / Questions / 10811 / ... Cela dit, je m'inscris fermement à cette philosophie: "Les conflits avec une politique d'école ou d'instructeur sur l'aide extérieure sont la responsabilité de l'étudiant posant la question, pas la communauté." Alors arrêtons déjà de gémir à ce sujet.
Je ne pense pas qu'une trie aide vraiment ici car la nouvelle lettre n'est pas toujours annexée
@Angoman, quel est le verdict?
Ce n'est pas difficile de dire ce qui est demandé ici »du tout. Vous êtes des gens noix.