Quero construir um gráfico a partir de uma lista de palavras comDistância de Hamming de (digamos) 1 ou, em outras palavras, duas palavras serão conectadas se diferirem apenas de uma letra (eisl ->eist)

de modo que dado

words = [ lol, lot, bot ]

o gráfico seria

{
  'lol' : [ 'lot' ],
  'lot' : [ 'lol', 'bot' ],
  'bot' : [ 'lot' ]
}

A maneira mais fácil é comparar todas as palavras da lista e contar os diferentes caracteres; infelizmente, este é umO(N^2) algoritmo.

Qual algo / ds / estratégia posso usar para obter melhor desempenho?

Além disso, vamos assumir apenas caracteres latinos, e todas as palavras têm o mesmo comprimento.