JAVA solution || DFS || Backtracking || full explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    boolean [][] visited;\n    int n,m;\n    public boolean exist(char[][] board, String word) {\n        n=board.length;\n        m=board[0].length;\n        visited=new boolean[n][m];\n\n        for(int i=0;i<n;i++){\n            for(int j=0;j<m;j++){\n                if(board[i][j]==word.charAt(0)){\n                    if(valid(i,j,0,board,word)){\n                        return true;\n                    }\n                }\n            }\n        }\n        return false;\n    }\n\n    public boolean valid(int i,int j,int count,char [][] board,String word){\n        /*-------------base conditions-------------*/\n        //out of bound\n        if(i<0 || i>=n || j<0 || j>=m ){\n            return false;\n        }\n\n        //if already visited\n        if(visited[i][j]){\n            return false;\n        }\n\n        //mismatch\n        if(word.charAt(count)!=board[i][j]){\n            return false;\n        }\n\n        //if word is found\n        if(count==word.length()-1){\n            return true;\n        }\n\n        /*----------------calculation and recursive calls----------*/\n\n        //mark current visited\n        visited[i][j]=true;\n\n        //inc count\n        count++;\n\n        //down,right,up,left search\n        if(valid(i+1,j,count,board,word) ||\n           valid(i,j+1,count,board,word) ||\n           valid(i-1,j,count,board,word) ||\n           valid(i,j-1,count,board,word) ){\n               return true;\n           }\n        \n        //mark current cell unvisited\n        visited[i][j]=false;\n        \n        return false;\n\n    }\n\n}\n```
['Array', 'Backtracking', 'Matrix', 'Java']