Spelling
SRM 75 · 2002-03-26 · by lbackstrom
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.
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
{"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.
{"topcoder","appirio"}
"aqpiri"
Returns: 3
One missing character, as well as a changed character. (p->q, and the o is missing from the end)
{"topcoderevent"}
"appirio"
Returns: -1
No matches.
Submissions are judged against all 81 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Spelling with a public method int distance(vector<string> dictionary, string word) · 81 test cases · 2 s / 256 MB per case