Given a list of word and a target word, output all the words for each the edit distance with the target no greater than k.
e.g. [abc, abd, abcd, adc], target “ac”, k = 1,
output = [abc, adc]
A naive solution would be, for each word in the list, calculate the edit distance with the target word. If it is equal or less than k, output to the result list. If we assume that the average length of the words is m, and the total number of words in the list is n, the total time complexity is O(n * m^2).
The problem with the previous solution is if the given list of the words is like ab, abc, abcd, each time we need to repeatedly calculate the edit distance with the target word. If we can combine the prefix of all words together, we can save lots of time.
Explanation will be added.
Always welcome new ideas and
practical tricks, just leave them in the comments!