Java || 0ms || Fast || Explanation of optimizations
The Java code below runs at 0ms in April 2024.  \n\n---\nFast solutions previously on the runtime graph with coding errors\nUpdate:  As of November 2022, the ru
The Java code below runs at 0ms in April 2024.  \n\n---\n**Fast solutions** previously **on the runtime graph with coding errors**\nUpdate:  As of November 2022, the runtime graph has been reset.  The code from the runtime graph that is discussed in this section, no longer appears on the runtime graph but may still appear in some discussion/solution entries.\n\n(Outdated)  On the graph of execution times for this leetcode problem, there are multiple bars on the graph with fast execution times in the range 0ms to 5ms, but the example code for those bars have a flaw that can produce a wrong answer with some test cases.  By clicking on those faster bars of the graph, I have found the example code for that bar.  Many of these code examples from the graph have special handling for the following test case from this leetcode problem:\n```\n        [["A","B","C","E"],["S","F","E","S"],["A","D","E","E"]]\n        "ABCESEEEFS"\n```\nWithout the special checks for this test case, some of those code examples would get the wrong answer.  In example code for 0ms on the execution-time graph, if the passed word is the word from the above test case, then the code immediately returns `true`, because without this check the code would give the wrong result.  Some other examples from the fastest bars of the graph look at surrounding board squares in an order which allows this test case to be accepted, because they look in the valid direction first.  For the fastest code examples from the execution-time graph that correctly handle the above case, most will get the wrong answer for a test case:\n```\n        [["A","B","C","E"],["S","F","E","S"],["A","D","E","E"],["A","D","E","E"]]\n        "ABCESEEEEEFS"\n```\nThe flaw in these fastest code examples is that they keep a flag for each board square, which indicates if that square has been searched with a specific index into the word and that search failed.  This optimization flag is used to stop extra searches at a board square with the same index into the word.  But this optimization is flawed because it doesn\'t handle a board square being searched at the same index into the word, but where the search path through the board may approach the same square at the same word index from **different directions** of approach to that square.  In the above test cases, the many "E"s on the board and many "E"s in the word can cause many paths through the board\'s "E"s to be searched.  Not all of these paths lead to a valid solution.  The optimization flags for the squares do not contain any information as to which direction that board square was approached from.  \n\nAn example from the above test cases showing how this optimization fails, is that an "E" on the board may be searched with, for example, the 3rd "E" of the word and that path through the board eventually doesn\'t match the word.  Then that "E" on the board is flagged as already having been tried with the 3rd letter of the word and that search failed.  But a later search path through the board approaches that same "E" on the board but from a different direction and wants to use that "E" from the board for the 3rd "E" of the word.  But that board square already has that "E"\'s square flagged as having failed when trying to use it for the 3rd "E" of the word.  So that optimization flag causes that search to be terminated early as a failure, when that "E" could actually have been used to match the 3rd "E" of the word as part of a valid match for the entire word.  In this case, these optimization flags prevent a valid word match from being found.  In most test cases, this optimization works to produce the correct answer, but for some situations such as the above test cases, this optimization can fail.\n\n---------\n**Explaining the code below.**\n\nThe Java code example below uses a Depth First Search (DFS) to recursively try many paths on the board to try to match the passed word.  The DFS recursively looks for the next letter in the word in the surrounding squares (up, down, left, right) of the board.  If the DFS successfully searches to the end of the word, then the DFS returns `true` unwinding back through the recursive calls, and the search is terminated with a success in finding the word on the board.\n\nSeveral optimizations to try to decide the answer before starting the DFS are used to make the code faster.  These optimizations are described in paragraphs below.\n\n**Optimization - Check if word can fit on the board:**  If the word has more letters than the board has squares, then return false because the word is too long to fit on the board.  Within the documented constraints of this leetcode problem, the worst case that this optimization prevents is a 3x4 `board` of all the same letter, with a 13-letter `word` of all that same letter.  If the DFS searching was done on this worst case example, it would waste a lot of time searching many many paths but never finding a solution.  In fact, this is an actual leetcode test case:\n```\n        [["a","a","a","a"],["a","a","a","a"],["a","a","a","a"]]\n        "aaaaaaaaaaaaa"\n```\n**Optimization - Put the word String into a char array:**  The code below could have been written to access the String `word` using `word.charAt(i)`, and the code would still work correctly.  But instead the Stringf `word` is copied into a `char` array named `wordc`.  There is some overhead time to allocate the char array, then to copy the String.  But with many repeated access to the characters in the word, it is faster to access a char array than to access the String.\n\nAnother faster method of accessing the letters of the word, would be to copy the word to a `byte` array, which is possible because the word only uses ASCII characters, which all fit into the low 7-bits of a byte.  Therefore the code:\n```\n        byte[] wordc = new byte[word.length()];\n\t\tword.getBytes(0, word.length(), wordc, 0);\n```\nwill use a `byte` array that can be faster than a `char` array.  But this method is not the best programming practices because it does not correctly handle Unicode characters.  However, if working on a project that has strict timing requirements, and Unicode is not used, then using this form of `getBytes` may be needed to meet the timing requirements.  \n\n**Optimization - Check if all word letters are on the board:**  The biggest improvement in speed came from checking if all the letters in the word exist somewhere on the board.  If the word contains a letter not found on the board, then return `false` and don\'t waste time doing the DFS.  To do this check, scan the word, building a count of the number of occurrences of each letter in the word.  Then scan the entire board building a count of the number of occurrences of each letter on the board.  Compare the counts of the letters in the word and the letters on the board.  If a letter in the word does not have enough of that letter on the board, then return false because the word cannot exist on the board.  The advantage of this optimization is best shown with the leetcode problem\'s actual test case:\n```\n        [["A","A","A","A","A","A"],["A","A","A","A","A","A"],\n        ["A","A","A","A","A","A"],["A","A","A","A","A","A"],\n        ["A","A","A","A","A","A"],["A","A","A","A","A","A"]]\n        "AAAAAAAAAAAAAAB"\n```\nWithout this optimization and the following optimization, the recursive Depth First Search would waste time searching through all of the "A"s.  This optimization would detect that the "B" in the word does not exist on the board, and would quickly return a false.\n\n**Optimization - Reverse word if word\'s last letter appears less frequently on the board:**  There is no difference in the final answer if the word is found on the board by scanning forward through the word, or by scanning backward through the word.  But a speed improvement can be gained by starting the Depth First Search (DFS) from the word\'s first letter or last letter, whichever occurs least on the board.  Using the letter counts from the previous optimization, if the last letter in `word` occurs less that the first letter of `word`, then simply reverse the letters in the word.  Reversing the word, allows the DFS to be simpler and faster code that always processes the letters in the word in a forward direction.  For example, if the `word` being searched for is "AAAAAB" and the board has many "A"s but has only a few "B"s, then it reverses the word to "BAAAAA" before searching the board.\n\n**Optimization - Scan `board` for first letter of the `word`:**  With nested row and column loops, scan the board, looking for only the first letter of the word, before starting a recursive DFS search at a board square that contains the word\'s first letter.  Using a simple `if` to look for the first letter of the word, is faster than doing a DFS at each square of the board.\n\n**If useful, please upvote.**\n\n**--- Clean code ---**\n(Commented code further below)\n```\npublic class Solution {\n    public boolean exist(final char[][] board, final String word) {\n        if (word.length() > board.length * board[0].length)  \n            return false;\n        \n        final int[] freqForBoard = new int[128]; \n        final int[] freqForWord = new int[128]; \n        char[] wordc = word.toCharArray();\n        for (int cc : wordc)  \n            freqForWord[cc]++; \n        for (int r = board.length - 1; r >= 0; r--) \n            for (int c = board[0].length - 1; c >= 0; c--) \n                freqForBoard[board[r][c]]++; \n        for (int cc : wordc) \n            if (freqForBoard[cc] < freqForWord[cc]) \n                return false; \n\n        if (freqForBoard[wordc[0]] > freqForWord[wordc[wordc.length - 1]]) {\n            for (int left = wordc.length / 2 - 1, right = (wordc.length + 1) / 2; \n                                left >= 0; ) {\n                final char temp = wordc[left];\n                wordc[left--] = wordc[right];\n                wordc[right++] = temp;\n            }\n        }\n\n        final boolean[][] visited = new boolean[board.length][board[0].length];\n        final char firstChar = wordc[0];\n        for (int r = 0; r < board.length; r++) \n            for (int c = 0; c < board[0].length; c++) \n                if ((firstChar == board[r][c]) && search(board, wordc, r, c, 0, visited)) \n                    return true;\n        \n        return false;\n    }\n    \n    private boolean search(char[][] board, char[] wordc, int r, int c, \n                           int index, boolean[][] visited) {\n        if (board[r][c] != wordc[index] || visited[r][c]) \n            return false;\n        if (index == wordc.length - 1) \n            return true;\n        \n        visited[r][c] = true;\n        if ((r > 0                   && search(board, wordc, r-1, c, index+1, visited)) || \n            (r < board.length - 1    && search(board, wordc, r+1, c, index+1, visited)) ||\n            (c > 0                   && search(board, wordc, r, c-1, index+1, visited)) || \n            (c < board[0].length - 1 && search(board, wordc, r, c+1, index+1, visited)))\n            return true;\n        visited[r][c] = false;\n        return false;\n    }\n}\n```\n**--- Commented code ---**\n```\npublic class Solution {\n    public boolean exist(final char[][] board, final String word) {\n        // If word is longer than the board has letters, then \n        // word cannot be on the board.\n        if (word.length() > board.length * board[0].length)  \n            return false;\n        \n        // Make sure the board contains all the letters in the word, \n        // while not checking the positions of those letters.  \n        // Just check the count of each unique letter on the board \n        // and in the word.\n        final int[] freqForBoard = new int[128]; \n        final int[] freqForWord = new int[128]; \n        char[] wordc = word.toCharArray();\n        for (int cc : wordc)                        // Count letters in word.\n            freqForWord[cc]++; \n        for (int r = board.length - 1; r >= 0; r--) // Count letters on board.\n            for (int c = board[0].length - 1; c >= 0; c--) \n                freqForBoard[board[r][c]]++; \n        for (int cc : wordc)                        // Test for enough letters.\n            if (freqForBoard[cc] < freqForWord[cc]) \n                return false; \n\n        // If first letter in word has a higher count on the board \n        // then the last letter in word, then reverse the letters \n        // in word so we start the search with the least used letter \n        // from either end of the word.\n        if (freqForBoard[wordc[0]] > freqForWord[wordc[wordc.length - 1]]) {\n            for (int left = wordc.length / 2 - 1, right = (wordc.length + 1) / 2; \n                                left >= 0; ) {\n                final char temp = wordc[left];\n                wordc[left--] = wordc[right];\n                wordc[right++] = temp;\n            }\n        }\n\n        // Scan the board for the first letter of the word.  (Remember \n        // that the word may have been reversed.)  If first letter found, \n        // then call recursive routine to search for the rest of the word.\n        final boolean[][] visited = new boolean[board.length][board[0].length];\n        final char firstChar = wordc[0];\n        for (int r = 0; r < board.length; r++) \n            for (int c = 0; c < board[0].length; c++) \n                if ((firstChar == board[r][c]) && search(board, wordc, r, c, 0, visited)) \n                    return true;\n        \n        return false;\n    }\n    \n    \n    // Recursively look for the next letter of the word, until \n    // the end of the word, or next letter not found.\n    private boolean search(char[][] board, char[] wordc, int r, int c, \n                           int index, boolean[][] visited) {\n        if (board[r][c] != wordc[index] || visited[r][c]) \n            return false;\n        if (index == wordc.length - 1) \n            return true;\n        \n        visited[r][c] = true;\n        if ((r > 0                   && search(board, wordc, r-1, c, index+1, visited)) || \n            (r < board.length - 1    && search(board, wordc, r+1, c, index+1, visited)) ||\n            (c > 0                   && search(board, wordc, r, c-1, index+1, visited)) || \n            (c < board[0].length - 1 && search(board, wordc, r, c+1, index+1, visited)))\n            return true;\n        visited[r][c] = false;\n        return false;\n    }\n}\n```
['Java']