martes, 4 de marzo de 2014

Crear un diccionario de anagramas a partir de una lista en Python

Hoy tuve una entrevista de trabajo, y esta fue una de las 3 preguntas que me hicieron. Teniendo una lista de palabras, agrupar todas en grupos de anagramas. Aunque al principio le di muchas vueltas a una idea de analizar y eliminar, mi solución apuntaba a una eficiencia O(n*n), y me pidieron que lo hiciera lineal. Ahí fue donde se me ocurrió que entonces guardara todo conforme iba recorriendo la lista:
__author__ = 'frcelaya'

def groupAnagrams(wordList):
  anagramsDic = {}
  for word in wordList:
    sortedWord = ''.join(sorted(word))
    if sortedWord not in anagramsDic.keys():
        anagramsDic[sortedWord] = [word]
    else:
        anagramsDic[sortedWord].append(word)

  return anagramsDic

def main():
    wordList = ["casa", "aacs", "perro", "saca", "platano", "amarillo", "rrope"]

    print groupAnagrams(wordList)


if __name__ == '__main__':
    main()
Siento que quedó bien.

2 comentarios:

  1. Pero si trabajas en Intel, como es que te quieres salir de ahí; Fue mi primer pensamiento..
    Y a dónde quieres ir ahora, Fer?

    ResponderEliminar
  2. Nel! Se acabó mi contrato en enero :(

    Estoy aplicando a una empresa llamada Ooyala, es de software y se ve muy chila.

    ResponderEliminar

Deja algo lindo, especial, original y coherente =)