C++ | DFS | 2 Methods 0(n) & O(1) | Backtracking
\n\nMethod - 1:\nO(n * word size)\nn = rowscol\n\nclass Solution {\npublic:\n    \n    bool search(vector<vector<char>>& board, int i, int j, string& word, int 
![image](https://assets.leetcode.com/users/images/17498125-18a3-44f1-8921-caf9419ced12_1633608296.9319909.png)\n\n***Method - 1:***\nO(n * word size)\nn = rows*col\n```\nclass Solution {\npublic:\n    \n    bool search(vector<vector<char>>& board, int i, int j, string& word, int pos, vector<vector<bool>>& visited){\n        if(pos == word.length() - 1)\n            return true;\n        \n        visited[i][j] = true;\n        \n        if(i > 0 && !visited[i-1][j] && board[i-1][j] == word[pos+1] &&search(board ,i-1 ,j ,word, pos+1, visited))\n            return true;\n        if(j > 0 && !visited[i][j-1] && board[i][j-1] == word[pos+1] &&search(board ,i ,j-1 ,word, pos+1, visited))\n            return true;\n        if(i < board.size()-1 && !visited[i+1][j] && board[i+1][j] == word[pos+1] &&search(board ,i+1 ,j ,word, pos+1, visited))\n            return true;\n        if(j < board[0].size()-1 && !visited[i][j+1] && board[i][j+1] == word[pos+1] &&search(board ,i ,j+1 ,word, pos+1, visited))\n            return true;\n        \n        visited[i][j] = false;\n        return false;\n    }\n    \n    bool exist(vector<vector<char>>& board, string word) {\n        \n        vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));\n        for(int i = 0; i < board.size(); i++)\n            for(int j = 0; j < board[0].size(); j++)\n                if(board[i][j] == word[0] && search(board,i,j,word,0,visited))\n                    return true;\n        \n        return false;\n    }\n};\n```\n\n***Method - 2:***\n0(1)\n```\nclass Solution {\npublic:\n    \n    bool search(vector<vector<char>>& board, int i, int j, string& word, int pos){\n        if(pos == word.length() - 1)\n            return true;\n        \n        /* ASCII value of A-Z : 65-90 && a-z : 97-122\n         That\'s why i took 65, i.e ASCII value of A so that when i subtract it goes out of range of a-z & A-Z \n         U can take any other no. also but after subtracting it should go out of range of words\n        It works similar as visited just having less space now*/\n        board[i][j] -= 65;\n        \n        if(i > 0 && board[i-1][j] == word[pos+1] && search(board ,i-1 ,j ,word, pos+1))\n            return true;\n        if(j > 0 &&  board[i][j-1] == word[pos+1] && search(board ,i ,j-1 ,word, pos+1))\n            return true;\n        if(i < board.size()-1 && board[i+1][j] == word[pos+1] &&search(board ,i+1 ,j ,word, pos+1))\n            return true;\n        if(j < board[0].size()-1 && board[i][j+1] == word[pos+1] &&search(board ,i ,j+1 ,word, pos+1))\n            return true;\n        \n        board[i][j] += 65;\n        return false;\n    }\n    \n    bool exist(vector<vector<char>>& board, string word) {\n        \n        for(int i = 0; i < board.size(); i++)\n            for(int j = 0; j < board[0].size(); j++)\n                if(board[i][j] == word[0] && search(board,i,j,word,0))\n                    return true;\n        \n        return false;\n    }\n};\n```\nHope you liked it , kindly upvote !!\n\nHappy Coding \uD83E\uDD17\n\n\n
['Backtracking', 'Depth-First Search', 'Recursion', 'C', 'C++']