Skip to main content
Eu mudei a apresentação do código, e coloquei o highlight code do python.
Fonte Link
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('')

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('')
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('')

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('')
Fonte Link

Como melhorar o custo de tempo do algoritmo - Python

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('')