| | Class name: Spell
Method name: getAlternatives
Parameters: String[], String, int
Returns: String[]
A spell checker finds good alternatives for a misspelled word by finding all
words in its dictionary with a certain degree of similarity to the misspelled
word. The trick is in measuring similarity.
One good method is to measure what is called the Levenshtein distance between
two words. The Levenshtein distance between a pair of words is a measure of
the cost of transforming one word to another. Possible transform operations
are to delete a character, to insert a character, and to replace one character
with any other character. While there are an infinite number of sequences of
transformations that can be used, the Levenshtein distance is the least cost.
For this problem, the cost of a deletion, insertion, or replace is 1
transformation. Thus, the Levenshtein distance will be the smallest number of
transformation operations that will convert one word to another. For example,
the Levenshtein distance between the words "cat" and "car" is 1: the only
transformation needed is to replace the 't' with 'r'. The Levenshtein distance
between the words "Levenshtein" and "Liechtenstein" is 5: insert an 'i' after
the 'L', replace the 'v' with a 'c' and insert 'h' and 't' immediately after
it, and delete the 'h'.
Implement a class named Spell that implements a method named getAlternatives.
The method takes a String[], a String, and an int as its parameters. The
method signature is:
public String[] getAlternatives(String[] dict, String word, int min);
The first parameter, dict, is a String[]. Each String in dict is a word in the
dictionary. These words will be in no particular order.
The second parameter, word, is the misspelled word for which we are seeking
alternatives.
The final parameter, min, governs how similar the returned words must be.
The method should return an String[], containing all the words in the
dictionary that are possible alternatives to the given word.
The String[] dict will contain at least one and most 50 elements. Each element
in the String[] dict will contain at least one and at most 50 letters (a-z,
A-Z). The elements in the String[] will be unique. The String word will
contain at least one and at most 50 letters. The String word will not be in
the String[] dict. The integer min will be a positive integer less than 1000.
To decide whether or not a word in the dictionary is a potential alternative,
the Levenshtein distance between it and the misspelled word must be calculated.
If the Levenshtein distance is less than or equal to the value of min, then
that word is considered to be a valid alternative.
Notes:
-Return the words in the same relative order they were inputted.
-The spell checker should be case sensitive. (The Levenshtein distance between
"hi" and "Hi" is 1.
Examples:
Let the dictionary contain the following words:
dispel
impel
mill
misdeal
misdeed
misspell
sell
spell
topcoder
If the given word is "mispell", then the Levenshtein distances are as follows:
dispel -> mispell = 2
impel -> mispell = 3
mill -> mispell = 3
misdeal -> mispell = 2
misdeed -> mispell = 3
misspell -> mispell = 1
sell -> mispell = 3
spell -> mispell = 2
topcoder -> mispell = 8
Therefore, if min = 2, the method should return:
[dispel, misdeal, misspell, spell]
If
dict=["north","south","east","west","northeast","southwest","compass","note","so
up"] and word="weast" and min=3, the method should return:
["east","west"]
If
dict=["different","difference","differentiate","differentiated","differentiates"
,"same"] and word="dffrntiatd" and min=4, the method should return:
["differentiate","differentiated"]
If dict=["no","similarities","here"] and word="longincorrectword" and min=4,
the method should return [] (an empty String[]).
|