Boa noite galera !! Estou com o seguinte problema nesse algoritmo, o custo dele ainda está alto e eu gostaria de saber se tem como melhorar o custo dele ainda mais, pois essa é uma questão de ortografia que tenho que entregar online e infelizmente um teste deu um custo de tempo alto cerca de 3s, caso tiver alguma ideia de como poderia melhorar ficaria muito grato, ou se souber algum Levenshtein mais rápido com um custo melhor de tempo, também ficaria muito grato, vou deixa o link da questão caso queiram fazer alguns teste https://olimpiada.ic.unicamp.br/pratique/p2/2008/f2/ortografia/
n, m = [int(c) for c in input().split()]
dicionario = [0] * n
palavras = [0] * m
for i in range(n):
n = input()
dicionario[i] = n.lower()
for i in range(m):
m = input()
palavras[i] = m.lower()
def levenshteinDistance(s1, s2):
if len(s1) > len(s2):
s1, s2 = s2, s1
distances = range(len(s1) + 1)
for i2, c2 in enumerate(s2):
distances_ = [i2+1]
for i1, c1 in enumerate(s1):
if c1 == c2:
distances_ += [distances[i1]]
else:
distances_ += [1 + min((distances[i1], distances[i1 + 1], distances_[-1]))]
distances = distances_
return distances[-1]
for i in range(len(palavras)):
lis = []
for n in dicionario:
if len(n) <= len(palavras[i]) + 2 or len(n) < len(palavras[i]) + 2:
if levenshteinDistance(palavras[i], n) <= 2:
lis += [n]
else:
pass
palavras[i] = lis
print(' '.join(palavras[i]), end="")
if palavras[i] != palavras[-1]:
print(" ", end='')
print('')