Buttercola: Airbnb: K Edit Distance
Airbnb: K Edit Distance
Question:
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]
Naive Solution:
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).
A better solution with a trie:
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.
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]
Naive Solution:
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).
A better solution with a trie:
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.
Read full article from Buttercola: Airbnb: K Edit Distance
No comments:
Post a Comment