Quiero construir un gráfico a partir de una lista de palabras conDistancia de Hamming de (digamos) 1, o para decirlo de otra manera, dos palabras están conectadas si solo difieren de una letra (lol ->lot)

así que dado

words = [ lol, lot, bot ]

el gráfico sería

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

La manera más fácil es comparar cada palabra de la lista entre sí y contar los diferentes caracteres; tristemente, este es unO(N^2) algoritmo.

¿Qué algo / ds / estrategia puedo usar para lograr un mejor rendimiento?

Además, supongamos solo caracteres latinos, y todas las palabras tienen la misma longitud.