Question

Write a spell checker class that stores a set of words, W, in a hash table and implements a function, spellCheck(s), which performs a Spell Check on the string s with respect to the set of words, W. If s is in W, then the call to spellCheck(s) returns an iterable collection that contains only s, since it is assumed to be spelled correctly in this case. Otherwise, if s is not in W, then the call to spellCheck(s) returns a list of every word in W that could be a correct spelling of s. Your program should be able to handle all the common ways that s might be a misspelling of a word in W, including swapping adjacent characters in a word , inserting a single character inbetween two adjacent characters in a word, deleting a single character from a word, and replacing a character in a word with another character. for an extra challenge, consider phonetic substitutions as well.

I am having a hard time following this,I've seen other posts that answer this, but when I try to run it I get a lot of errors. The language is C++. Id love it to be easy to understand as in teling me this part is for the header file , or this textfile needs to be added under the source file. Thankyou so much!!

Answer 1

The following code uses famous algorithm to find out the matching words using distance.

Code:

#include <string>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iostream>

std::size_t nearestMatchAlg( std::string word, std::string match )
{
if( match.size() < word.size() ) std::swap(word,match) ;
std::vector<std::size_t> temp( match.size()+1 ), previous(temp) ;
std::iota( previous.begin(), previous.end(), 0 ) ;

for( std::size_t i = 0 ; i < word.size() ; ++i )
{
temp[0] = i+1 ;
for( std::size_t j = 0 ; j < match.size() ; ++j )
{
temp[j+1] = std::min( std::min( temp[j], previous[j+1]) + 1,
previous[j] + ( word[i] != match[j] ) ) ;
}
temp.swap(previous);
}
return previous.back() ;
}

std::vector<std::string> nearestMatchingWords( const std::string& word, const std::vector<std::string>& dict )
{
constexpr std::size_t MAX_DIFF = 5 ;
std::vector<std::string> nearest[MAX_DIFF+1] ;
for( const std::string match : dict )
{
std::size_t dist = nearestMatchAlg( word, match ) ;
if( dist <= MAX_DIFF ) nearest[dist].push_back(match) ;
}

for( const auto& seq : nearest ) if( !seq.empty() ) return std::move(seq) ;
return {} ;
}

int main()
{
const std::vector<std::string>& dict { "alpha", "alphine", "algae", "ball", "bell", "beat", "flu", "plu" } ;
const std::string test[] = { "aloaa", "bsll", "belk"} ;
for( const std::string& word : test )
{
std::cout << word << " => " ;
for( const auto& nearest : nearestMatchingWords( word, dict ) ) std::cout << nearest << ' ' ;
std::cout << '\n' ;
}
}

Sample output:

aloaa => alpha algae
bsll => ball bell
belk => bell

Screenshots:

'

In case of any doubts, please comment.