Un amateur a travaillé sur le Google Tech Dev Guide, un matériel d'apprentissage fourni par Google, mais comme il est un étranger, le contenu ne vient pas lors de la lecture en anglais. Je l'ai traduit en japonais car il serait plus efficace de le lire après l'avoir entièrement traduit en japonais. J'espère que cela aide quelqu'un.
Cette fois, j'ai travaillé sur les éléments suivants:
■ Titre Former Coding Interview Question: Find longest word in dictionary that is a subsequence of a given string
■ Lien https://techdevguide.withgoogle.com/paths/foundational/find-longest-word-in-dictionary-that-subsequence-of-given-string/#code-challenge
・ Mis en œuvre avec Python 3.6 ・ J'ai fait quelque chose d'équivalent à l'algorithme Greedy lié sans aucun effort particulier.
def find_longest_word_in_string(letter, words):
i = 0
ok = ""
l = len(letter) - 1
for w in words:
j = 0
while j < l:
if w[0] == letter[j]:
j += 1
w = w[1:]
else:
j +=1
if w == "":
if len(ok) < len(words[i]):
ok = words[i]
i += 1
return(ok)
S = "abppplee"
D = ["jam", "jamboleeee", "able", "ale", "apple", "bale", "kangaroo"]
result = find_longest_word_in_string(S, D)
print(result)
Traduction japonaise de l'explication ci-dessous.
■ Explication Diverses méthodes peuvent être considérées comme une approche de résolution de problèmes (Par exemple, il existe plusieurs algorithmes applicables). En d'autres termes, votre capacité et vos connaissances à résoudre des problèmes seront testées.
■ Solution forcée Générez toutes les sous-chaînes possibles de 2 ^ n à partir de la chaîne S et vérifiez si elles correspondent aux mots du dictionnaire D. Pour une petite optimisation, la chaîne à comparer doit être représentée par une table de hachage ou une arborescence de préfixes pour rendre la recherche plus efficace.
■ Vérifiez chaque mot du dictionnaire avec la méthode gourmande Il peut être confirmé par la méthode gloutonne si le mot w dans le dictionnaire D est une sous-chaîne de S. Balayez S pour w [0] depuis le début. Lorsque w [0] est trouvé dans S, continuez à rechercher w [1] à partir de l'emplacement où w [0] a été trouvé, jusqu'à ce que tout le S soit balayé ou que tous les caractères contenus dans w soient trouvés. continuer.
Après avoir trié dans l'ordre décroissant selon la longueur des mots contenus dans D, la procédure ci-dessus peut être exécutée, et le premier mot qui devient une sous-chaîne de S peut être utilisé comme résultat de détection. Le temps d'exécution est O (N * W) à partir du nombre de mots W contenus dans le dictionnaire et du nombre de caractères N inclus dans S.
Si la longueur du mot contenu dans D est proche de N dans la longueur de S, le temps d'exécution O (N * W) est progressivement optimal (car l'entrée est O (N * W)). Cependant, dans le pire des cas, si la chaîne de caractères S est longue et les mots contenus dans D sont très courts, elle est loin d'être optimale.
Soit L la longueur totale des lettres de tous les mots contenus dans le dictionnaire. Dans ce cas, le meilleur cas de temps de calcul est O (N + L) (en considérant le cas où le mot est plus court que S). Cependant, le temps d'exécution de l'algorithme ci-dessus est O (N * W), et il peut être O (N * L) lorsque les mots contenus dans le dictionnaire ont une certaine petite longueur.
■ Comment améliorer la cupidité Pour vérifier le mot w dans le dictionnaire, il faut connaître le minimum i pour lequel la lettre c contenue dans w a S [i] == c plus grande que la position j où la lettre correspond à S avant. Soyez conscient de cela. La méthode gourmande est évidemment lente car elle scanne ce i sans réfléchir.
Le prétraitement S peut rendre ces opérations beaucoup plus rapides. Faites une carte de caractères-> Faites une liste triée par caractère. Par exemple, si S == "abppplee":
a -> [0] b -> [1] p -> [2, 3, 4] l -> [5] e -> [6, 7]
Lorsque vous voulez savoir "Où correspondait la lettre suivante Y, la lettre précédente était X?" Recherchez Y sur la carte, puis effectuez une dichotomie pour trouver la plus petite position de X dans la liste. Trouvez le numéro ou constatez qu'il n'existe pas (auquel cas les mots sont dans le désordre dans le S).
Cette méthode nécessite une dichotomie pour chaque caractère contenu dans D. Par conséquent, dans ce cas, puisque seul O (N) est nécessaire pour le prétraitement de S, le temps de traitement total devient O (N + logN) * 1 et se rapproche du meilleur temps de traitement possible.
Approche plus avancée: Puisqu'il s'agit d'un problème classique de "valeur de successeur", vous pouvez constater qu'il existe des structures de données spéciales qui peuvent effectuer des recherches encore plus rapidement. Par exemple, l'utilisation de l'arborescence vEB améliore le temps d'exécution à O (N + L * loglogN).
■ Approche optimale de O (N + L) pour les chaînes de petite taille (je ne suis pas sûr ici) Si la taille de la chaîne de caractères n'est que de a-z ou d'un certain petit nombre, elle peut être résolue par le temps d'exécution de O (N + L) mentionné ci-dessus.
Le temps d'exécution réel est O (N * A + L), où A est le nombre d'alphabets. Au lieu de créer une expression creuse * 2 (vous pourriez la rendre dense). ← Je ne suis pas sûr. Au lieu de p-> [2, 3, 4], vous pouvez p-> [2, 2, 3, 4, -1, -1, -1, -1, -1], et le i-ième index va directement à la requête Générez une réponse. Cette méthode nécessite un espace O (N) pour chaque caractère (O (NA) au total), et le prétraitement prend du temps. Par conséquent, il ne convient pas aux chaînes de caractères volumineuses.
■ Le meilleur moyen pour n'importe quelle chaîne Traitez tous les mots en même temps au lieu de traiter mot par mot.
Tout d'abord, créez un taple contenant w et 0 pour chaque mot w contenu dans D (par exemple (w, 0)). Ce numéro est la lettre contenue dans w trouvée dans S, donc aucun n'a été trouvé au début. À propos de taple t Soit le mot tapple t.w et le nombre contenu dans tapple t.i (car c'est un index).
Regroupez les mots par t.w [t.i](la valeur initiale de t.i est 0, donc la valeur initiale est le premier caractère). Par exemple, dans l'exemple, D = {"able", "ale", "apple", "bale", "kangaroo"}, donc
a -> [("able", 0), ("ale", 0), ("apple", 0)] b -> [("bale", 0)] k -> [("kangaroo", 0)]
Ce que nous faisons ici montre quels mots rechercher ensuite pour les lettres qui pourraient être trouvées dans le S.
Scannez caractère par caractère pour S. Si le caractère scanné est c, t.i est incrémenté de 1 pour chaque taple inclus dans la carte [c] et déplacé vers la carte [t.w [t.i]] * 3. Si t.i == t.w.length, déplacez-le vers la liste des mots spéciaux "trouvés". La sortie finale du programme est le mot le plus long de la liste trouvée.
Vérifiez l'opération en copiant et en commentant tout en regardant l'écran. (L'exemple de réponse d'origine doit corriger l'indentation de l'instruction if à la ligne 35)
#!/usr/bin/env python
import collections
import sys
import logging
logging.basicConfig(level = logging.DEBUG, format = "%(asctime)s - %(levelname)s - %(message)s")
logging.disable(logging.DEBUG)
def find_longest_word_in_string(letters, words):
letter_positions = collections.defaultdict(list)
#Pour créer une liste qui ne nécessite pas d'initialisation. Utilisez defaultdict.
for index, letter in enumerate(letters):
letter_positions[letter].append(index)
#Extrayez les caractères des lettres comme clés de dictionnaire.
#Enregistrez la position de la lettre en lettres dans une liste dans le dictionnaire.
#la clé est la lettre.
for word in sorted(words, key=lambda w: len(w), reverse=True):
#Trier les mots des mots par ordre décroissant de longueur
pos = 0
for letter in word:
logging.debug("word is {}, letter is {}." .format(word, letter))
if letter not in letter_positions:
break
#Le caractère est lettre_pause sinon en position
possible_positions = [p for p in letter_positions[letter] if p >= pos]
#p est la position de la lettre cible. Même si l'instruction if au milieu de la boucle for est interrompue, pos est ajouté, donc
#Le personnage suivant est la cible du jugement.
logging.debug("possible_positions are {}." .format(possible_positions))
logging.debug("pos is {}." .format(pos))
if not possible_positions:
break
logging.debug("possible_positions[0] is {}." .format(possible_positions[0]))
pos = possible_positions[0] + 1
#possible_positin[0]Renvoie le premier nombre de la liste qui stocke la position de la lettre.
#Par ↑, le caractère à juger en lettres est mis au caractère après la lettre courante.
#Exemple: lettres= "aaapplle"、word = "apple"dans le cas de,
#La lettre de la boucle du premier tour est"a"Parce que c'est possible_positions = (0, 1, 2)
#La pos de la boucle suivante est 0+ 1 = 1
#Dans la boucle suivante, la lettre est"p"Parce que c'est possible_positions = (3, 4)
#La pos de la boucle suivante est 3+ 1 = 4
#Dans la boucle suivante, la lettre est"p"Mais p>=Parce que la condition est de 4 ou plus que pos
#possible_positions = (4)
#Si pour tourne jusqu'à ce qu'il n'y ait plus de caractères dans le mot, il ne sera pas cassé et le mot sera retourné.
else:
return word
#print(find_longest_word_in_string(sys.argv[1], sys.argv[2:]))
#Exécutez en spécifiant une chaîne de caractères et un mot à partir de la ligne de commande.
if __name__ == '__main__':
letters = "abppplee"
words = ["able", "ale", "apple", "bale", "kangaroo"]
print(find_longest_word_in_string(letters, words))
#Si vous exécutez le fichier de script directement à partir de la ligne de commande,__name__Automatiquement dans la variable (attribut)
# __main__L'opération «de substitution» est effectuée au tout début.
・ Cela prend du temps par le nombre de caractères x le nombre de mots, c'est lent ・ Au moins, j'aurais dû trier par longueur de mot et casser au milieu ・ Il est important de concevoir le prétraitement des données
Recommended Posts