[peff]

You can store the values in a trie (e.g., with one node per character in the string). Exact lookup in the trie is O(string_length), like a hash table. Inexact lookup can similarly walk the tree, but explore side branches within a certain budget.

So if your string is "abc", you'd follow the node for "a", then the one for "b", but _also_ the one for "c", at a cost of 1 (because dropping the "b" incurs an edit distance of 1).

[DAllison]

> Exact lookup in the trie is O(string_length), like a hash table

It's worth noting that some standard libraries (Java's JDK for one [1]) will cache the value of String.GetHashCode(), meaning string lookup in a HashTable is constant time average (but O(n) worst-case due to collisions).

[1]: http://mindprod.com/jgloss/hashcode.html