My DFS + Backtracking C++ solution (16ms)
Typical dfs+backtracking question. It compare board[row][col] with word[start], if they match, change board[row][col] to '' to mark it as visited. Then move to 
Typical dfs+backtracking question. It compare board[row][col] with word[start], if they match, change board[row][col] to '*' to mark it as visited. Then move to the next one (i.e. word[start+1]) and compare it to the current neighbors ( doing it by recursion)\n\n    class Solution {\n    private:\n        bool dfs(vector<vector<char>>& board, int row, int col, const string &word, int start, int M, int N, int sLen)\n        {\n            char curC;\n            bool res = false;\n            if( (curC = board[row][col]) != word[start]) return false;\n            if(start==sLen-1) return true;\n            board[row][col] = '*';\n            if(row>0) res = dfs(board, row-1, col, word, start+1, M, N, sLen);\n            if(!res && row < M-1) res = dfs(board, row+1, col, word, start+1, M, N, sLen);\n            if(!res && col > 0)   res = dfs(board, row, col-1, word, start+1, M, N, sLen);\n            if(!res && col < N-1) res = dfs(board,  row, col+1, word, start+1, M, N, sLen);\n            board[row][col] = curC;\n            return res;\n        }\n        \n    public:\n        bool exist(vector<vector<char>>& board, string word) {\n            int M,N,i,j,sLen = word.size();\n            if( (M=board.size()) && (N=board[0].size()) && sLen)\n            {\n                for(i=0; i<M; ++i)\n                    for(j=0; j<N; ++j)\n                        if(dfs(board, i, j, word, 0, M, N, sLen)) return true;\n            }\n            return false;\n        }\n    };
[]