[pyar] Ejercicio (para entretenerse)

[fisa]

El día 13 de enero de 2012 14:31, fisa <fisadev en gmail.com> escribió:
> 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)
>


Aclaro que no usé ningún tipo se sort (y eso hizo que el código sea
bastante más feo) para que sea O(N), ya que un sort de cualquier tipo
sería peor que O(N).


-- 
fisa  -  Juan Pedro Fisanotti