Does the trie help in memoizing the edit distance between multiple words? Or do you pay the O(n^2) cost per word? I'd love to hear details of how this works!
With brute-force you have no idea about what letters could follow a given letter, but with a Trie you already know the possible combinations so you avoid needless permutations.