Problem Statement
A spell checker must use some way to determine which words to suggest when a word not in its dictionary is encountered. This is usually done by some sort of distance metric that determines the distance between two words. The words that have the least distance are then suggested. Your task is, given a dictionary (as a String[]), you must determine which word from the dictionary is closest to the given word, and return the distance between the two words.
Distance is calculated as follows:
- Change a character to another character: +1
- Insert a character into the given word: +2
- Delete a character from the given word: +3
However, because people usually do not leave out or insert more than one character, your method may either insert or delete one character at most, but not both. However, the method may change letters in addition to adding or deleting.
If no words from the dictionary have length within one of the given word, return -1.
Definition
- Class:
- Spelling
- Method:
- distance
- Parameters:
- String[], String
- Returns:
- int
- Method signature:
- int distance(String[] dictionary, String word)
- (be sure your method is public)
Notes
- If the dictionary is empty, return -1.
Constraints
- - Each word in the dictionary, and the given word, will contain only the lower case letters 'a' to 'z', inclusive.
- - Each word in the dictionary, and the given word, will have between 1 and 50 characters, inclusive.
- - dictionary will contain between 0 and 50 words, inclusive
Examples
{"topcoder"}"topcoder"
Returns: 0
Perfect match.{"topcoder"}"tppcoder"
Returns: 1
One character mistyped.{"topcoder","topcod"}"topcode"
Returns: 2
When multiple dictionary words could be the match, pick the one that scores lowest.{"topcoderevent"}"appirio"
Returns: -1
No matches.