viernes, 21 de febrero de 2014

Anagramas con Python

Hoy resolví un examen en el que necesitaba checar dos arreglos, y que la palabra arreglo_a[i] fuera un anagrama de arreglo_b[i]. Lo resolví en Python de dos maneras:
__author__ = 'frcelaya'


def check_anagrams(first_words, second_words):
    if len(first_words) != len(second_words):
        print "Arrays are not of the same size"
        return
    for i, word in enumerate(first_words):
        if len(first_words[i]) == len(second_words[i]):
            is_anagram = True
            copy = second_words[i]
            for letter in word:
                if letter in copy:
                    pos = copy.index(letter)
                    copy = copy[:pos] + copy[(pos+1):]
                else:
                    is_anagram = False
                    break
            if is_anagram:
                print 1
            else:
                print 0
        else:
            print 0
    return


def check_anagrams2(first_words, second_words):
    if len(first_words) != len(second_words):
        print "Arrays are not of the same size"
        return
    for i, word in enumerate(first_words):
        a = sorted(first_words[i])
        b = sorted(second_words[i])
        if a == b:
            print 1
        else:
            print 0


def main():
    import time
    first_words = ["cinema", "host", "aba", "train", "adela"]
    second_words = ["iceman", "shot", "bab", "rain", "aleda"]

    start = time.time()
    check_anagrams(first_words, second_words)
    end = time.time()
    print "Check_Anagrams time:", end-start

    start2 = time.time()
    check_anagrams2(first_words, second_words)
    end2 = time.time()
    print "Check_Anagrams2 time:", end2-start2


if __name__ == "__main__":
    main()
La segunda es un poco más rápida, pero siendo sinceros, fue inspirada en un post en Stack Overflow. La primera la pensé yo solito. Por ahí vi otra solución sobre llenar unas tablas de frecuencias, pero estas dos soluciones me parecieron más sencillas y entendibles. En cuanto a eficiencia, me exigían que se resolviera en 2 segundos, no tuve problemas con eso.

No hay comentarios.:

Publicar un comentario

Deja algo lindo, especial, original y coherente =)