✅ Java, beats 99.3%, DFS, Explained with dry-run on paper
If you\'ll like the explanation, do UpVote :)\n### Dry run\n\n\n\t --------------\n\t\t--------------\n\n\nNote: \nDo check Solution 2 as well, which is even mo
If you\'ll like the explanation, do **UpVote** :)\n### Dry run\n\n![image](https://assets.leetcode.com/users/images/e9f9212a-f900-44e0-9d46-69a6ff3245ca_1647315994.8879087.png)\n\t --------------\n\t\t--------------\n\n\n**Note:** \nDo check **Solution 2** as well, which is even more optimized  (Runtime: 55 ms, **faster than 99.20%**)\n\t\n### Solution 1 (Very short & Simple code)\n\tclass Solution {\n\t\tpublic boolean exist(char[][] board, String word) {\n\t\t\tint rows = board.length, cols = board[0].length;                                // length of rows & columns \n\t\t\tif(word.length() == 0){ return true; }                                          // if "word" is empty, we will just return true. \n\t\t\tif(rows * cols < word.length()){ return false; }                                // if board size (rows*cols) < word length, => word has some character(s) not present in board. So, just return False. This is optimized way as we are avoiding doing DFS search in such test cases. \n\n\t\t\t// Traverse all chars of board\n\t\t\tfor(int r = 0; r < rows; r++){\n\t\t\t\tfor(int c = 0; c < cols; c++){\n\t\t\t\t\tif(board[r][c] == word.charAt(0)){                                                // keep iterating until we don\'t find first character of "word"\n\t\t\t\t\t\tboolean isFound = dfsBoard(board, new boolean[rows][cols], r, c, word, 0);    // call DFS or recursion\n\t\t\t\t\t\tif(isFound){ return true; }\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\n\t\t\treturn false;                                                                             // if we traveresed all chars of board, it means we did not find all chars of word. so return false\n\t\t}\n\t\t// ----------------------------------------------------------------------------------------------------------------------------------------------- //\n\t\tpublic boolean dfsBoard(char[][] board, boolean[][] visitedBoard, int row, int col, String word, int wordInd) {        \t\t\t\n\t\t\tif( (row < 0 || row >= board.length)   ||   (col < 0 || col >= board[0].length)  ||   board[row][col] != word.charAt(wordInd) ){\n\t\t\t\treturn false;                                                                             // return false, if:  a)  row or col goes out of bound.  b) char in board != char in word \n\t\t\t}\n\t\t\tif(visitedBoard[row][col] ){ return false; }                                                  // this element already visited, so don\'t do DFS on this\n\t\t\tif(wordInd == word.length() - 1){ return true; }\n\t\t\tvisitedBoard[row][col] = true;                                                                // mark it as visited now             \n\t\t\t\t\n\t\t\tif( dfsBoard(board, visitedBoard, row, col-1, word, wordInd + 1) ){ return true; }            // DFS on Left\n\t\t\tif( dfsBoard(board, visitedBoard, row, col+1, word, wordInd + 1) ){ return true; }            // DFS on Right\n\t\t\tif( dfsBoard(board, visitedBoard, row-1, col, word, wordInd + 1) ){ return true; }            // DFS on ABove\n\t\t\tif( dfsBoard(board, visitedBoard, row+1, col, word, wordInd + 1) ){ return true; }            // DFS on Below\n\t\t\tvisitedBoard[row][col] = false;\n\t\t\treturn false;\n\t\t}\n\t}\n\n//\n//\n//\n//\n//\n//\n//\n\n### Solution 2 (More Optimized)\nJust added a new method **checkWordCharactersInBoard()**\n\t\n\tclass Solution {\n\t\tpublic boolean exist(char[][] board, String word) {\n\t\t\t// Here, same code as in Solution 1\n\t\t\tif(! checkWordCharactersInBoard(board, rows, cols, word) ){ return false; }                         // check if board contains all chars of word. \n\t\t\t// Here, same code as in Solution 1\t\t\n\t\t}\n\n\t\t// ----------------------------------------------------------------------------------------------------------------------------------------------- //\n\t\tpublic boolean dfsBoard(char[][] board, boolean[][] visitedBoard, int row, int col, String word, int wordInd) {         \n\t\t\t// same code as in Solution 1\n\t\t}\n\n\t\t// ----------------------------------------------------------------------------------------------------------------------------------------------- //\n\t\tpublic boolean checkWordCharactersInBoard(char[][] board, int rows, int cols, String word){              //   This method helped reducing Runtime further to only 55ms\n\t\t\tList<Character> wordList = new LinkedList<Character>();\n\t\t\tfor(char ch : word.toCharArray()){ wordList.add(ch); }\n\t\t\tfor(int r = 0; r < rows; r++){\n\t\t\t\tfor(int c = 0; c < cols; c++){\n\t\t\t\t\tchar ch = board[r][c];\n\t\t\t\t\tif(wordList.size() == 0){ return true; }\n\t\t\t\t\tif(wordList.contains(ch) ){ wordList.remove((Character)ch); }                \n\t\t\t\t}\n\t\t\t}\n\t\t\tif(wordList.size() == 0){ return true; }\n\t\t\treturn false;\n\t\t}\n\t}\n\t\n//\n//\n//\n//\n//\n//\n//\nYou can talk about Solution 2, if you are asked to optimize further. \n## For coding interviews:\n\t1. You can discuss Solution 1 first, and then optimize using Solution 2 (instead of directly jumpting to optimized solution) in coding interview. \n\nIf you like the explanation, do **UpVote** :)\nIf you need more explanation or, if got even more optimized way, **comment** below.
['Depth-First Search', 'Java']