C++ backtracking solution without extra data structure
Use board itself to mark whether we have visited it before.\n\n    class Solution {\n    public:\n        bool exist(vector>& board, string word) {\n           
Use board itself to mark whether we have visited it before.\n\n    class Solution {\n    public:\n        bool exist(vector<vector<char>>& board, string word) {\n            if (board.size() == 0) return false;\n            for (int i=0; i<board.size(); ++i) {\n                for (int j=0; j<board[i].size(); ++j) {\n                    if (search(board, word, i, j, 0)) return true;\n                }\n            }\n            return false;\n        }\n        \n        bool search(vector<vector<char>>& board, string word, int i, int j, int pos) {\n            \n            if (pos == word.size()) return true;\n            if ((i<0) || (i >= board.size()) || (j <0) || (j >= board[i].size())) return false;\n            char c = board[i][j];\n            if (c == word[pos]) {\n                board[i][j] = '#';\n                if (search(board, word, i - 1, j, pos + 1)) return true;\n                if (search(board, word, i+1, j, pos+1)) return true;\n                if (search(board, word, i, j-1, pos+1)) return true;\n                if (search(board, word, i, j+1, pos+1)) return true;\n                board[i][j] = c;\n            }\n            return false;\n            \n        }\n    };
['C++']