# T9

16.20 T9: On old cell phones, users typed on a numeric keypad and the phone would provide a list of words that matched these numbers. Each digit mapped to a set of 0 - 4 letters. Implement an algorithm to return a list of matching words, given a sequence of digits. You are provided a list of valid words (provided in whatever data structure you'd like). The mapping is shown in the diagram below:

``````EXAMPLE
Input: 8733
Output: tree, used``````
• There are few approaches to this problem.

• 1) Brute force. Check every combination of characters

``````class cellPhone_word {
public:
cellPhone_word(string dictionaryPath) {
// preprocess file
std::ifstream file;
if (file.good()) {
file.open(dictionaryPath, std::fstream::in);
}

// assuming dictionary is well formatted.

string word;
while (file >> word) {
// first concatenate the digits that form the word
string digit_s = "";
for (auto &i : word) {
digit_s += char_to_digit.find(i)->second;
}

// map to hash map
// if word exists, then add to vector
auto &find = main_map.find(digit_s);
if (find == main_map.end()) {
vector<string> *newVec = new vector<string>;
newVec->push_back(word);
main_map.insert({ { digit_s }, { newVec } });
}
// found so just insert word to key
else {
find->second->push_back(word);
}
}
}

vector<string>* getWords(string key) {
return main_map.find(key)->second;
}

private:
// need to use string, since words can be extremely long
unordered_map<string, vector<string>*> main_map;

const map<const char, const char> char_to_digit =
{
{ { 'a' },{ '2' } }, { { 'b' },{ '2' } }, { { 'c' },{ '2' } },
{ { 'd' },{ '3' } }, { { 'e' },{ '3' } }, { { 'f' },{ '3' } },
{ { 'g' },{ '4' } }, { { 'h' },{ '4' } }, { { 'i' },{ '4' } },
{ { 'j' },{ '5' } }, { { 'k' },{ '5' } }, { { 'l' },{ '5' } },
{ { 'm' },{ '6' } }, { { 'n' },{ '6' } }, { { 'o' },{ '6' } },
{ { 'p' },{ '7' } }, { { 'q' },{ '7' } }, { { 'r' },{ '7' } },
{ { 's' },{ '7' } }, { { 't' },{ '8' } }, { { 'u' },{ '8' } },
{ { 'v' },{ '8' } }, { { 'w' },{ '9' } }, { { 'x' },{ '9' } },
{ { 'y' },{ '9' } }, { { 'z' },{ '9' } }
};

};

int main()
{
const string filepath = "C:/Users/Gamer/Desktop/C++ Daily/words.txt";
cellPhone_word test(filepath);

vector<string>* strings = test.getWords("8733");
for (auto &s : *strings) cout << s << " ";
cout << endl;
}``````

Last updated