C++  & Python Solution || DFS Traversal || Backtracking (Easiest Solution)🔥✅
C++ Solution\n\n// If it helps plz upvote :)\n\nclass Solution {\nprivate:\n    bool dfs(vector<vector<char>> &board,vector<vector<int>> &visited,string &word,i
**C++ Solution**\n```\n// If it helps plz upvote :)\n\nclass Solution {\nprivate:\n    bool dfs(vector<vector<char>> &board,vector<vector<int>> &visited,string &word,int i,int j,int idx){\n        // base case\n        if(idx == word.size()) return true;\n\n        if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || visited[i][j] == 1 || board[i][j] != word[idx]){\n            return false;\n        }\n\n        // Marking visited\n        visited[i][j] = 1;\n\n        // traversing all side\n        bool ls = dfs(board,visited,word,i,j-1,idx+1); // left\n        bool rs = dfs(board,visited,word,i,j+1,idx+1); // right\n        bool ds = dfs(board,visited,word,i+1,j,idx+1); // down\n        bool us = dfs(board,visited,word,i-1,j,idx+1); // up\n\n        // Backtracking (If no one is found suitable match)\n        visited[i][j] = 0;\n\n        return ls | rs | ds | us;\n    }\npublic:\n    bool exist(vector<vector<char>>& board, string word) {\n        int n = board.size();\n        int m = board[0].size();\n        vector<vector<int>> visited(n,vector<int>(m,0));\n\n        for(int i=0;i<n;i++){\n            for(int j=0;j<m;j++){\n                if(visited[i][j] == 0 && word[0] == board[i][j]){\n                    if(dfs(board,visited,word,i,j,0)){\n                        return true;\n                    }\n                }\n            }\n        }\n\n        return false;\n    }\n};\n\n// If it helps plz upvote :)\n```\n\n\n---\n\n**Python Solution**\n```\nclass Solution:\n    def __init__(self):\n        self.visited = []\n\n    def solve(self, board, word, i, j, idx):\n        n, m, sz = len(board), len(board[0]), len(word)\n\n        # Base case\n        if idx == sz:\n            return True\n\n        # Checking if index is out of bound or current word not not matching with the word at current position at board or it is already visited or not\n        if i == n or j == m or i < 0 or j < 0 or self.visited[i][j] == 1 or board[i][j] != word[idx]:\n            return False\n\n        self.visited[i][j] = 1\n\n        # Traversing all sides and checking each possibility\n        c1 = self.solve(board, word, i+1, j, idx+1)\n        c2 = self.solve(board, word, i-1, j, idx+1)\n        c3 = self.solve(board, word, i, j+1, idx+1)\n        c4 = self.solve(board, word, i, j-1, idx+1)\n\n        self.visited[i][j] = 0\n\n        # Returning true if we get true from any possibility\n        return c1 or c2 or c3 or c4\n        \n    def exist(self, board: List[List[str]], word: str) -> bool:\n        n, m = len(board), len(board[0])\n        self.visited = [[0 for _ in range(m)] for _ in range(n)] \n\n        for i in range(0, n):\n            for j in range(0, m):\n                if board[i][j] == word[0]:\n                    if self.solve(board, word, i, j, 0) == True:\n                        return True\n        \n\n        return False\n```
['Backtracking', 'Depth-First Search', 'C', 'C++']