C++ Memoisation | Clean Solution
Premature optimization is the root of all evil  ( Donald Knuth)\n\nThe problem is pretty straightforward in its approach: you are asked to compute the minimum d
`Premature optimization is the root of all evil  ( Donald Knuth)`\n\nThe problem is pretty straightforward in its approach: you are asked to compute the minimum distance to type a word using two fingers. The logical question boils down to with which finger do you write every letter in the word. You have only two fingers (two choices) so let the program decide that for you.\n\nThe choices: either type the letter at position `word_pos` with the first finger or with the second\n```\ndist = min(x + minimumDistanceHelper(word, word_pos + 1, keyboard[word[word_pos]], finger_2_pos, mem),\n                   y + minimumDistanceHelper(word, word_pos + 1, finger_1_pos, keyboard[word[word_pos]], mem));\n```\n```\nclass Solution {\npublic:\n\n    map<char, pair<int, int>> keyboard;\n\n    int minimumDistanceHelper(string word, int word_pos, pair<int, int> finger_1_pos, pair<int, int> finger_2_pos, vector<vector<vector<int>>>& mem) {\n        if (word_pos == word.size()) {\n            return 0;\n        }\n\n        if(finger_2_pos.first != -1) {\n            if (mem[word_pos][6 * finger_1_pos.first + finger_1_pos.second][6 * finger_2_pos.first +\n                                                                            finger_2_pos.second] != -1)\n                return mem[word_pos][6 * finger_1_pos.first + finger_1_pos.second][6 * finger_2_pos.first +\n                                                                                   finger_2_pos.second];\n        }\n\n        int x = abs(finger_1_pos.first - keyboard[word[word_pos]].first) +\n                abs(finger_1_pos.second - keyboard[word[word_pos]].second);\n        int y = finger_2_pos.first == -1 ? 0 : abs(finger_2_pos.first - keyboard[word[word_pos]].first) +\n                                               abs(finger_2_pos.second - keyboard[word[word_pos]].second);\n        int dist;\n\n        dist = min(x + minimumDistanceHelper(word, word_pos + 1, keyboard[word[word_pos]], finger_2_pos, mem),\n                   y + minimumDistanceHelper(word, word_pos + 1, finger_1_pos, keyboard[word[word_pos]], mem));\n\n        if(finger_2_pos.first != -1) {\n            mem[word_pos][6 * finger_1_pos.first + finger_1_pos.second][6 * finger_2_pos.first +\n                                                                        finger_2_pos.second] = dist;\n        }\n        return dist;\n    }\n\n    int minimumDistance(string word) {\n        for (char i = \'A\'; i <= \'Z\'; ++i) {\n            keyboard[i] = make_pair((i - \'A\') / 6, (i - \'A\') % 6);\n        }\n\n        vector<vector<vector<int>>> mem(word.size(),\n                                        vector<vector<int>>(keyboard.size(), vector<int>(keyboard.size(), -1)));\n        return minimumDistanceHelper(word, 1, make_pair(keyboard[word[0]].first, keyboard[word[0]].second),\n                                     make_pair(-1, -1), mem);\n\n\n    }\n};\n```
[]