The main objective of a best-matching algorithm for words is to find the words most similar to a string passed as a parameter. To implement one of these algorithms, you need the following:
- A list of words: In our case, we have used the UK Advanced Cryptics Dictionary (UKACD), which is a word list compiled for the crossword community. It has 250,353 words and idioms. It can be downloaded for free from http://www.crosswordman.com/wordlist.html.
- A metric to measure the similarity between two words: We have used the Levenshtein distance that is used to measure the difference between two sequences of characters. The Levenshtein distance is the minimal number of insertions, deletions, or substitutions that is necessary to transform the first string into the second string. You can find a brief description of this metric at https://en.wikipedia.org/wiki/Levenshtein_distance.
In our example, you will implement two operations:
- The first operation returns...