49. Group Anagrams

Sommaire

Description

Approche

Réflexions clés

Erreurs commises à éviter

Rectifications

En savoir plus sur la série Arrays and Hashing

Description

Given an array of strings strs, group the anagrams together. You can return the answer in any order. An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Étant donné un tableau de chaînes de caractères strs, regroupez les anagrammes. Vous pouvez renvoyer la réponse dans n'importe quel ordre. Une anagramme est un mot ou une phrase formé en réarrangeant les lettres d'un autre mot ou d'une autre phrase, en utilisant généralement toutes les lettres originales une seule fois.

Approche

On a approché le problème en sachant qu’il fallait réutiliser notre algorithme pour détecter des anagrammes valides. La difficulté se trouvait dans la construction de la solution souhaitée. On a donc commencé par une approche brute force pour traiter tous les cas et obtenir le bon format de retour et set pour répertorier les cas déjà vus. Ensuite, nous avons éliminé petit à petit les cas qui ne valaient pas la peine d’être traités.

Réflexions clés

• Encore une fois, notre solution penche d’un coté de la balance entre une bonne complexité temps et une bonne complexité espace. Dans ce cas ci, on a plutôt une bonne complexité espace. Mais nous avons un peu de mal à imaginer une solution pour améliorer le runtime de notre code à notre niveau actuel.

• Une implémentation intelligente de la solution en utilisant un dictionnaire avec comme clé le string trié et comme valeurs le mot.

• La meilleure solution implémentée en python est aussi une solution similaire à celle précédente avec la vérification en plus que le mot trié ne soit pas déjà dans le dictionnaire de retour.

Cette solution fait donc un runtime beaucoup plus petit que la solution que nous avons proposé. Encore une fois, c’est notre méconnaissance des structures de données qui nous fait défaut.

Erreurs commises à éviter

• Store dans notre set les valeurs de la liste de strings. Nous sommes passés coté du fait que si dans la liste en entrée on a deux éléments identiques alors, il ne sont pas pris en compte.

• Une structure conditionnelle non optimisé nous faisait perdre beaucoup de temps.

Rectifications

• Nous avons remplacé les valeurs de la liste de strings en entrée par ses indices.

• Pour régler la problème de runtime, on a améliorer nos structures conditionnelles

En savoir plus sur la série Arrays and Hashing

Cet article touche à sa fin, mais notre exploration des Arrays et Hashing ne fait que commencer. Ne manquez pas nos autres articles de la série pour approfondir vos connaissances, surtout si vous débutez ! Apprenez de mes expériences et progressez avec nous.