Building graph of "adjacent" strings

I've got a set of strings, and need to build a graph where strings are the nodes, and there's an edge between any pair of adjacent strings.

To strings A and B are said to be adjacent if by adding, removing, or replacing a sing开发者_开发问答le character of A (at whatever position) you get B.

For example scar and car are adjacent (removing the s from scar), so are car and far (replacing c with f) and so are far and farm (adding m).

Is it possible to do this in less than O(n^2)?

You have to compute n(n - 1)/2 = O(n^2) entries in the adjacency matrix (the entries are 1 if the Levenshtein distance is 1, and 0 otherwise). There is no way to avoid this.

(Note that given n, I can find an alphabet and a collection of words on that alphabet such that all n words are neighbors and the graph would be complete.)

I think it is not possible.

In the worst case, all words are neighbors. Example 6 words={cat, fat, rat, mat, sat, at}.

In this example you need to establish (n) * (n-1)/2 = 6 * 5/2 = 15 edges.

So you need O(n^2) operations just to set up the edges in the worst case ... no matter how many comparisons or loops you need, you can't better that.