Considera che l'algoritmo che cerchi di implementare non è comunque banale, soprattutto nel caso pessimo.
L'idea di concatenare le parole potrebbe migliorare un po' la situazione nei casi migliori ma la funzione Levenshtein ha comunque una complessità O(m * n).
Se le parole sono in ordine te la cavi con una complessità non troppo elevata in caso contrario dubito che tu possa evitare di eseguire una serie di cicli e di confronti.