[Java] Trie based Approach | Google asked
\nclass Solution {\n    TrieNode root;\n    int row, col;\n    public boolean exist(char[][] board, String word) {\n        //Approach - Trie Approach\n        
```\nclass Solution {\n    TrieNode root;\n    int row, col;\n    public boolean exist(char[][] board, String word) {\n        //Approach - Trie Approach\n        root = new TrieNode();\n        insertInTrie(word);\n        TrieNode curr = root;\n        row = board.length;\n        col = board[0].length;\n        for (int i = 0; i < row; i++){\n            for (int j = 0; j < col; j++){\n                char ch = board[i][j];\n                if(curr.children.containsKey(ch) && dfs(curr, board, i, j))\n                    return true;\n            }\n        }\n        return false;\n\n    }\n    private boolean dfs(TrieNode curr, char[][] board, int i, int j){\n\n        if (curr.isEnd) return curr.isEnd;\n        if(i < 0 || j <0 || i>= row || j >= col || !curr.children.containsKey(board[i][j])) return false;\n        char ch = board[i][j];\n        char temp = board[i][j];\n        board[i][j] = \' \';\n\n        if (dfs(curr.children.get(ch), board, i+1, j) || dfs(curr.children.get(ch), board, i-1, j)\n                || dfs(curr.children.get(ch), board, i, j+1) || dfs(curr.children.get(ch), board, i, j-1))\n            return true;\n\n        board[i][j] = temp;\n        return false;\n\n    }\n    private void insertInTrie(String word){\n        TrieNode curr = root;\n        for (int i = 0; i<word.length(); i++){\n            char c = word.charAt(i);\n            if (curr.children.containsKey(c)) {\n                curr = curr.children.get(c);\n                continue;\n            }\n            curr.children.put(c,new TrieNode());\n            curr = curr.children.get(c);\n        }\n        curr.isEnd = true;\n    }\n}\n    \nclass TrieNode{\n    Map<Character, TrieNode> children;\n    boolean isEnd;\n    TrieNode(){\n        children = new HashMap<>();\n        isEnd = false;\n    }\n}\n```
['Trie', 'Java']