100% Beats || Fully Explained Code with comments || 2 approaches
Intuition\n Describe your first thoughts on how to solve this problem. \n\nImagine a word search puzzle where you try to find words by connecting letters.\nThis
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nImagine a word search puzzle where you try to find words by connecting letters.\nThis code is like a super-smart helper that checks if a word can be found in the puzzle.\n\n\n**1. Check if the word is even possible:**\n- Make sure the word isn\'t too long to fit in the puzzle.\n- Count the letters in the puzzle to see if there are enough to make the word.\n\n**2. Search like a detective:**\n- Start at each letter in the puzzle and pretend to build the word.\n- Move up, down, left, or right (but not diagonally) to try to find the next letter.\nKeep track of where you\'ve been so you don\'t repeat letters.\nFound it!\n- If you can build the entire word, shout "Eureka! I found the word!"\n\n![Screenshot 2024-04-03 053907.png](https://assets.leetcode.com/users/images/723f5131-ff0b-4d6d-8dae-83b5449737dc_1712102961.348769.png)\n\n# This approach is beginner friendly but bit slow , read more for 100% beat approach\n# java code\n```\nclass Solution {\n    // Main function to check if the word exists in the maze\n    public boolean exist(char[][] maze, String word) {\n        // Iterate through each cell in the maze\n        for (int i = 0; i < maze.length; i++) {\n            for (int j = 0; j < maze[0].length; j++) {\n                // If the current cell matches the first character of the word, start searching\n                if (maze[i][j] == word.charAt(0)) {\n                    boolean ans = search(maze, word, i, j, 0);\n                    if (ans) {\n                        return ans; // If the word is found, return true\n                    }\n                }\n            }\n        }\n        return false; // If the word is not found in the maze, return false\n    }\n    \n    // Recursive function to search for the word starting from a given position in the maze\n    public static boolean search(char[][] maze, String word, int row, int col, int idx) {\n        // Base case: If the entire word has been found, return true\n        if (idx == word.length()) {\n            return true;\n        }\n\n        // Check for out-of-bounds or mismatched characters\n        if (row < 0 || col < 0 || row >= maze.length || col >= maze[0].length || maze[row][col] != word.charAt(idx)) {\n            return false;\n        }\n\n        // Mark the current cell as visited\n        maze[row][col] = \'*\';\n\n        // Define the possible directions to move in the maze\n        int[] r = { -1, 1, 0, 0 };\n        int[] c = { 0, 0, -1, 1 };\n\n        // Recursively search in all four directions from the current cell\n        for (int i = 0; i < c.length; i++) {\n            boolean ans = search(maze, word, row + r[i], col + c[i], idx + 1);\n            if (ans == true) {\n                return ans; // If the word is found, return true\n            }\n        }\n\n        // Backtrack: Restore the original character in the maze\n        maze[row][col] = word.charAt(idx);\n        return false; // If the word is not found starting from the current cell, return false\n    }\n}\n\n```\n\n\n# Note:  Below approach is bit tricky but it beats 100%  \n# Approach\n<!-- Describe your approach to solving the problem. -->\n**1. Basic Checks:**\n - If the word length is greater than the total number of cells on the board, it\'s impossible to find the word (return false).\n\n**2. Character Frequency:**\n- Count the frequency of each character in the board.\n- Early check: If any character in the word has a higher frequency than its corresponding character in the board, it can\'t exist (return false).\n\n**3. Backtracking Search:**\n- Iterate through each cell on the board.\n- For each cell, use a recursive helper function visit to explore neighboring cells.\n- Base case in visit: If the entire word is found (start reaches the word length), return true.\n- Check for invalid positions, already visited cells, and character mismatch.\n- If the current character matches, mark the cell as visited and recursively explore neighboring cells (up, down, left, right) using visit.\n- The search succeeds if a path is found that connects all characters in the word from the starting cell.\n- If no path is found after exploring all neighboring cells, backtrack and return false.\n# Key Points:\n\n- The code uses a depth-first search (DFS) approach to explore potential paths on the board.\n- The visited array prevents revisiting cells and getting stuck in infinite loops.\n- The early check based on character frequency avoids unnecessary exploration when the word can\'t exist due to insufficient characters.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nWorst-case: O(rows * cols * 4^(wordLength)): In the worst case, the code might need to explore all possible paths from each cell on the board. This can happen if the board is large, the word is long, and there are many potential paths to explore.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(rows * cols): The space complexity is dominated by the visited boolean array. It has dimensions rows x cols to keep track of visited cells during the backtracking search. This space complexity is considered linear with respect to the input size (board dimensions).\n\n# Java \n```\nclass Solution {\n    // Main function to check if the word exists on the board\n    public boolean exist(char[][] board, String word) {\n        int n = board.length; // Number of rows in the board\n        int m = board[0].length; // Number of columns in the board\n        \n        boolean[][] visited = new boolean[n][m]; // Array to keep track of visited cells\n        \n        char[] wordChar = word.toCharArray(); // Convert the word into a character array\n        \n        // Quick check: If the length of the word exceeds the total number of cells on the board, it can\'t exist\n        if (wordChar.length > n * m)\n            return false;\n        \n        int counts[] = new int[256]; // Array to store counts of each character\n        \n        // Count the occurrence of each character on the board\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                counts[board[i][j]]++;\n            }\n        }\n        \n        // Adjust the order of characters in the wordChar array based on their frequency counts to optimize search\n        int len = wordChar.length;\n        for(int i=0; i<len/2; i++) {\n            if(counts[wordChar[i]] > counts[wordChar[len - 1 - i]]) {\n                for(int j=0; j<len/2; j++) {\n                    char temp = wordChar[j];\n                    wordChar[j] = wordChar[len - 1 - j];\n                    wordChar[len - 1 - j] = temp;\n                }\n                break;\n            }\n        }\n        \n        // Decrease counts of characters in the word from the board\n        for (char c : wordChar) {\n            if (--counts[c] < 0)\n                return false; // If there are more occurrences of a character in the word than on the board, return false\n        }\n        \n        // Iterate through each cell in the board and start searching for the word\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                if (visit(board, wordChar, 0, i, j, n, m, visited))\n                    return true; // If the word is found starting from this cell, return true\n            }\n        }\n        return false; // If the loop completes without finding the word, return false\n    }\n\n    // Helper function to recursively search for the word starting from a given cell\n    private boolean visit(char[][] board, char[] word, int start, int x, int y,\n            int n, int m, boolean[][] visited) {\n        // Base case: If all characters in the word are found, return true\n        if (start == word.length)\n            return true;\n        \n        // Check for out-of-bounds, already visited cells, and character mismatch\n        if (x < 0 || x >= n || y < 0 || y >= m || visited[x][y])\n            return false;\n        \n        // If the current character in the word does not match the character on the board, return false\n        if (word[start] != board[x][y])\n            return false;\n        \n        visited[x][y] = true; // Mark the current cell as visited\n        \n        // Recursively search in all four directions from the current cell\n        boolean found = visit(board, word, start + 1, x + 1, y, n, m, visited)\n                || visit(board, word, start + 1, x - 1, y, n, m, visited)\n                || visit(board, word, start + 1, x, y + 1, n, m, visited)\n                || visit(board, word, start + 1, x, y - 1, n, m, visited);\n        \n        visited[x][y] = false; // Backtrack: Unmark the current cell as visited\n        \n        return found; // Return whether the word was found starting from the current cell\n    }\n}\n\n\n\n```\n# C++\n```\n#include <vector>\nusing namespace std;\n\nclass Solution {\npublic:\n    // Main function to check if the word exists on the board\n    bool exist(vector<vector<char>>& board, string word) {\n        int n = board.size(); // Number of rows in the board\n        int m = board[0].size(); // Number of columns in the board\n        \n        vector<vector<bool>> visited(n, vector<bool>(m, false)); // Array to keep track of visited cells\n        \n        // Convert the word into a character array\n        vector<char> wordChar(word.begin(), word.end());\n        \n        // Quick check: If the length of the word exceeds the total number of cells on the board, it can\'t exist\n        if (wordChar.size() > n * m)\n            return false;\n        \n        vector<int> counts(256, 0); // Array to store counts of each character\n        \n        // Count the occurrence of each character on the board\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                counts[board[i][j]]++;\n            }\n        }\n        \n        // Adjust the order of characters in the wordChar array based on their frequency counts to optimize search\n        int len = wordChar.size();\n        for (int i = 0; i < len / 2; i++) {\n            if (counts[wordChar[i]] > counts[wordChar[len - 1 - i]]) {\n                for (int j = 0; j < len / 2; j++) {\n                    char temp = wordChar[j];\n                    wordChar[j] = wordChar[len - 1 - j];\n                    wordChar[len - 1 - j] = temp;\n                }\n                break;\n            }\n        }\n        \n        // Decrease counts of characters in the word from the board\n        for (char c : wordChar) {\n            if (--counts[c] < 0)\n                return false; // If there are more occurrences of a character in the word than on the board, return false\n        }\n        \n        // Iterate through each cell in the board and start searching for the word\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                if (visit(board, wordChar, 0, i, j, n, m, visited))\n                    return true; // If the word is found starting from this cell, return true\n            }\n        }\n        return false; // If the loop completes without finding the word, return false\n    }\n\n    // Helper function to recursively search for the word starting from a given cell\n    bool visit(vector<vector<char>>& board, vector<char>& word, int start, int x, int y,\n            int n, int m, vector<vector<bool>>& visited) {\n        // Base case: If all characters in the word are found, return true\n        if (start == word.size())\n            return true;\n        \n        // Check for out-of-bounds, already visited cells, and character mismatch\n        if (x < 0 || x >= n || y < 0 || y >= m || visited[x][y])\n            return false;\n        \n        // If the current character in the word does not match the character on the board, return false\n        if (word[start] != board[x][y])\n            return false;\n        \n        visited[x][y] = true; // Mark the current cell as visited\n        \n        // Recursively search in all four directions from the current cell\n        bool found = visit(board, word, start + 1, x + 1, y, n, m, visited)\n                || visit(board, word, start + 1, x - 1, y, n, m, visited)\n                || visit(board, word, start + 1, x, y + 1, n, m, visited)\n                || visit(board, word, start + 1, x, y - 1, n, m, visited);\n        \n        visited[x][y] = false; // Backtrack: Unmark the current cell as visited\n        \n        return found; // Return whether the word was found starting from the current cell\n    }\n};\n\n```\n# Please upvote , it motivates me to write more solution\n\n![main-qimg-dd19ad82f9afcc414cdfc8ded048648e-lq.jpeg](https://assets.leetcode.com/users/images/a12f44e1-8c0a-48ca-9d70-4304e0672b8a_1712105261.602322.jpeg)\n\n\n
['Python', 'C++', 'Java']