def distance(a, b):
    a=" " + a
    b=" " + b
    dist=[]
    for i in range(0, len(a)):
        dist.append([0]*len(b))

    for i in range( len(a)):
        dist[i][0]=i
    for i in range( len(b)):
        dist[0][i]=i

    for j in range(1, len(b)):
        for i in range(1, len(a)):
            if a[i] == b[j]:
                dist[i][j]=dist[i-1][ j-1]
            else:
                dist[i][j] = min(
                        dist[i-1][j]+1, #deletion
                        dist[i][j-1]+1, #insertion
                        dist[i-1][ j-1]+1.5 ) #substitute
    return dist[-1][-1]

possible=[]
words=open('words', 'r')

inword="deffinetly"

for i in words:
    i=i[:-1]
    d=distance(i, inword)
    if d < len(inword)//2:
        possible.append([d,str(i)])
possible.sort()
print( possible)