Problem: On some old cellphones, there was not enough room for a complete keyboard and users had to use their keypad with 9 numbers to type out text. Each number corresponded to several possible characters. For example, typing 2 could mean either a, b, or c. If a user wanted to type out cat they would type 228, but 228 could also mean act or bat. Question: Given an input string of digits and a text file containing a list of all valid words, your goal is to produce a vector of possible, valid words in alphabetical order for the given string of digits. Please also leave a short description about the run time complexity of your algorithm. We have provided you with the following to help get you started. Feel free to modify however you want. A mapping from each number to its possible characters. A file containing a list of valid words and some starter code to open this file and read it into a vector. Some example test cases. Please do this question in c++. You may use the standard library and the catch test framework, but please dont use other third-party libraries. We also expect a solution that is uniquely yours. Looking up resources is fine, but looking up solutions is no fun. Feel free to handle edge cases/error handling however you feel is most appropriate. At Kodiak, we strive for clean, well-written code. Readability and a good set of tests count as much as the correctness of the code. Good luck!

#include #include #include #include #define CATCH_CONFIG_MAIN #include "catch.hpp" using namespace std; // Feel free to modify any of this starter code however you want. static const unordered_map> kT9Mapping{{2, {'a', 'b', 'c'}}, {3, {'d', 'e', 'f'}}, {4, {'g', 'h', 'i'}}, {5, {'j', 'k', 'l'}}, {6, {'m', 'n', 'o'}}, {7, {'p', 'q', 'r', 's'}}, {8, {'t', 'u', 'v'}}, {9, {'w', 'x', 'y', 'z'}}}; vector ReadWords() { vector valid_words; ifstream word_file("/home/coderpad/data/words.txt"); if (word_file.is_open()) { string word; while (getline(word_file, word)) { valid_words.push_back(word); } word_file.close(); } return valid_words; } vector GetPossibleWords(const string& number_string) { vector possible_words; // Please write your solution here. return possible_words; } bool PossibleWordsMatch(const vector& expected, const vector& computed) { return expected == computed; } /* Please briefly describe the run time of your solution below: * * */ TEST_CASE("Possible words match", "[GetPossibleWords]") { const auto word_list = ReadWords(); // Build your data structure to hold the valid words here and then pass it to GetPossibleWords. REQUIRE(PossibleWordsMatch({"act", "bat", "cat"}, GetPossibleWords("228"))); REQUIRE(PossibleWordsMatch({"kodiak"}, GetPossibleWords("563425"))); // Add your test cases here. }