[pyar] Ejercicio (para entretenerse)

[fisa]

El día 13 de enero de 2012 13:14, Lucio Torre <lucio.torre en gmail.com> escribió:
> On Fri, Jan 13, 2012 at 11:44 AM, Sebastian Bassi
> <sebastian.bassi en globant.com> wrote:
>> De casualidad encontré una página que propone el siguiente problema, lo
>> posteo porque se de varios que le gustan resolver estas cosas:
>
> Obviamente lo interesante aca es hacerlo en O(N), no O(N**2). Es
> decir, no podes hacer una funcion que sea is_anagram(w1, w2) y hacer
> todos contra todos.
>
> Lucio.

Asumiendo que el .get de los diccionarios es O(1), esto sería O(N) con
N = cantidad de palabras, no?

palabras = 'abracadabra beards breads constant learner myopic
relearn'.lower().split()
abecedario = 'abcdefghijklmnopqrstuvwxyz'

resultados = {}

for p in palabras:
    letras = {}
    for l in p:
        letras[l] = letras.get(l, 0) + 1

    hash = ''.join(l + str(letras.get(l,0)) for l in abecedario)

    resultados[hash] = resultados.get(hash, []) + [p,]

# esto es para mostrar los resultados, no entra dentro del O del
proceso para obtenerlos
print '\n'.join(' '.join(r)
                for r in resultados.values()
                if len(r) > 1)

-- 
fisa  -  Juan Pedro Fisanotti