# My 16ms C++ solution

• ``````class Solution {
bool **map;
int m, n;
bool exi(vector<vector<char>>& board, string word, bool **map, int x, int y) {
if (board[x][y] == word[0]) {
if (word.length() <= 1) return true;
map[x][y] = true;
if (x + 1 < m && map[x + 1][y] == false) {
if (exi(board, word.substr(1, word.length() - 1), map, x + 1, y)) return true;
}
if (x > 0 && map[x - 1][y] == false) {
if (exi(board, word.substr(1, word.length() - 1), map, x - 1, y)) return true;
}
if (y + 1 < n && map[x][y + 1] == false) {
if (exi(board, word.substr(1, word.length() - 1), map, x, y + 1)) return true;
}
if (y > 0 && map[x][y - 1] == false) {
if (exi(board, word.substr(1, word.length() - 1), map, x, y - 1)) return true;
}
}
map[x][y] = false;
return false;
}
public:
bool exist(vector<vector<char>>& board, string word) {
if (board.size() == 0 || board[0].size() == 0) return false;
n = board[0].size(), m = board.size();
map = (bool**)malloc(m * sizeof(bool*));
for (int i = 0; i < m; ++i) {
map[i] = (bool*)malloc(n * sizeof(bool));
memset(map[i], false, n * sizeof(bool));
}
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
if (exi(board, word, map, i, j)) {
for (int i = 0; i < m; ++i) free(map[i]);
free(map);
return true;
}
}
for (int i = 0; i < m; ++i) free(map[i]);
free(map);
return false;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.