C++: How to prune the DFS to 0ms
I assume that you know how the DFS works. Here\'s an implementation of a basic DFS without pruning.\n\n    bool search(int r, int c, size_t i, const string &wor
I assume that you know how the DFS works. Here\'s an implementation of a basic DFS **without pruning**.\n```\n    bool search(int r, int c, size_t i, const string &word, vector <vector <char>> &board) {\n        if(i == word.size()) {return true;} // found word!\n        else if(r < 0 || r >= (int) board.size() || c < 0 || c >= (int) board[0].size()) {return false;} // out of bounds\n        else if(board[r][c] != word[i]) {return false;} // current character doesn\'t match the board\n        \n        board[r][c] = \'#\'; // mark board[r][c] as already visited\n        \n\t\t// move up, down, left, and right and see if you can find word from there\n        bool ret = search(r - 1, c, i + 1, word, board) || search(r + 1, c, i + 1, word, board)\n                || search(r, c - 1, i + 1, word, board) || search(r, c + 1, i + 1, word, board);\n        \n        board[r][c] = word[i]; // unmark board[r][c]\n        return ret;\n    }\n    \n    bool exist(vector<vector<char>>& board, string word) {\n        int R = board.size(), C = board[0].size();\n        \n\t\t// See if you can find word, starting from every possible starting point in board[][]\n        for(int r = 0; r < R; ++r) {\n            for(int c = 0; c < C; ++c) {\n                if(search(r, c, 0, word, board)) {return true;}\n            }\n        }\n        return false;\n    }\n```\n\nNow, **three pruning steps**:\n\n1. If the total number of characters in the board is less than the number of characters in word, then you can obviously ```return false;``` immediately. Basically, this is when word wouldn\'t fit in the board at all.\n2. For every character in word, that character must appear in board the same number of times or greater. Basically, the number of occurrences of any character `c` in board must be >= the number of occurrences of `c` in word.\n\nAdding these two pruning methods reduced my runtime from around 380ms (the original non-pruned program) to 45ms.\n\n3. **Not so well-known (I think)**\nConsider `word = "aaaaaaaaaab"` and let board have all `a` except for one `b` in the lower-right corner. The problem is that when we try finding `word` from each starting point, we will find a lot of ways to construct `aaaaaaaaaa` each time, but we will never find that last `b` until our starting point is close the lower-right corner. For these cases, the non-pruned algorithm will be significantly slower.\n\nWe can **partially** optimize these sorts of test cases as follows: find the longest prefix and suffix in `word` that are each made up of the same character. For example, if `word = "aaaabccc"`, the longest prefix and suffix are length 4 and 3 respectively. **If the longest prefix is longer than the longest suffix, then reverse the string**. This makes it so that `word` having a very long prefix is a lot less likely. But in cases where the longest prefix/suffix have very close lengths, this won\'t really help. But for the LeetCode test data, this seems to generate a large speedup; I was able to get 0ms runtime when I submitted the following solution:\n\n```\nclass Solution {\npublic:\n    bool search(int r, int c, size_t i, const string &word, vector <vector <char>> &board) {\n        if(i == word.size()) {return true;}\n        else if(r < 0 || r >= (int) board.size() || c < 0 || c >= (int) board[0].size()) {return false;}\n        else if(board[r][c] != word[i]) {return false;}\n        \n        board[r][c] = \'#\';\n        \n        bool ret = search(r - 1, c, i + 1, word, board) || search(r + 1, c, i + 1, word, board)\n                || search(r, c - 1, i + 1, word, board) || search(r, c + 1, i + 1, word, board);\n        \n        board[r][c] = word[i];\n        return ret;\n    }\n    \n    bool exist(vector<vector<char>>& board, string word) {\n        int R = board.size(), C = board[0].size(), N = word.size();\n        \n        // Prune #1: If there aren\'t even enough letters in the board to fit word, then return false\n        if((int) word.size() > R * C) {return false;}\n        \n        // Prune #2: For each letter, the board must contain at least as many of that letter as word contains\n        int occ[128] = {};\n        for(const auto &v : board) {for(char c : v) {++occ[c];}}\n        for(char c : word) {\n            if(--occ[c] < 0) {return false;}\n        }\n        \n        // Prune #3: Find the longest prefix/suffix of the same character. If the longest suffix is longer\n        // than the longest prefix, swap the strigns (so we are less likely to have a long prefix with a lot\n        // of the same character)\n        int left_pref = word.find_first_not_of(word[0]);\n        int right_pref = word.size() - word.find_last_not_of(word.back());\n        if(left_pref > right_pref) {\n            reverse(word.begin(), word.end());\n        }\n        \n        // for every starting point, see if we can find word from there\n        for(int r = 0; r < R; ++r) {\n            for(int c = 0; c < C; ++c) {\n                if(search(r, c, 0, word, board)) {return true;}\n            }\n        }\n        return false;\n    }\n};\n```
['C']