# My C++ solution takes 88 ms, is there something wrong? how to enhance?

• ``````bool exist(vector<vector<char>>& board, string word) {
if (0 == word.length()) return false;
if (0 == board.size()) return false;
if (0 == board[0].size()) return false;

int row = board.size(), col = board[0].size(), size = word.length();

vector<int> wordRow(word.length(), 0);
vector<int> wordCol(word.length(), 0);

bool found = false;
char c = word[0];
for (int i=0; i<row; ++i) {
for (int j=0; j<col; ++j) {
if (c == board[i][j]) {
int idx = 0;
wordRow[idx] = i;
wordCol[idx] = j;
found = find(board, row, col, word, wordRow, wordCol, idx + 1, size);
}
if (found) break;
}
if (found) break;
}

return found;
}

bool find(vector<vector<char>>& board, int row, int col, string& word, vector<int>& wordRow, vector<int>& wordCol, int idx, int size) {
if (idx == size) return true;

int prevRow = wordRow[idx-1];
int prevCol = wordCol[idx-1];

bool found = false;
if (!found && prevRow+1 < row && board[prevRow+1][prevCol] == word[idx] &&
!isCircle(word, wordRow, wordCol, prevRow+1, prevCol, idx)) {
found = find(board, row, col, word, wordRow, wordCol, idx + 1, size);
}
if (!found && prevRow-1 >= 0  && board[prevRow-1][prevCol] == word[idx] &&
!isCircle(word, wordRow, wordCol, prevRow-1, prevCol, idx)) {
found = find(board, row, col, word, wordRow, wordCol, idx + 1, size);
}
if (!found && prevCol+1 < col && board[prevRow][prevCol+1] == word[idx] &&
!isCircle(word, wordRow, wordCol, prevRow, prevCol+1, idx)) {
found = find(board, row, col, word, wordRow, wordCol, idx + 1, size);
}
if (!found && prevCol-1 >= 0  && board[prevRow][prevCol-1] == word[idx] &&
!isCircle(word, wordRow, wordCol, prevRow, prevCol-1, idx)) {
found = find(board, row, col, word, wordRow, wordCol, idx + 1, size);
}

return found;
}

inline bool isCircle(string& word, vector<int>& wordRow, vector<int>& wordCol, int r, int c, int idx) {
bool circle = false;
for (int i=0; i<idx; ++i) {
if (word[i] == word[idx]) {
if (wordRow[i] == r && wordCol[i] == c) {
// There is a cycle, break;
circle = true;
break;
}
}
}
if (!circle) {
wordRow[idx] = r;
wordCol[idx] = c;
}
return circle;
}``````

• using a hash array (row*col) to store the previous checked point on the board instead of searching the previous items, make this solution as 16 ms.

• ``````// 16 ms
bool exist(vector<vector<char>>& board, string word) {
if (0 == word.length()) return false;
if (0 == board.size()) return false;
if (0 == board[0].size()) return false;

int row = board.size(), col = board[0].size(), size = word.length();

vector<int> boardCheck(row*col, 0);

bool found = false;
char c = word[0];
for (int i=0; i<row; ++i) {
for (int j=0; j<col; ++j) {
if (c == board[i][j]) {
int point = i*col+j;
boardCheck[point] = 1;
found = find(board, row, col, word, boardCheck, i, j, 1, size);
boardCheck[point] = 0;
}
if (found) break;
}
if (found) break;
}

return found;
}

bool find(vector<vector<char>>& board, int row, int col, string& word, vector<int>& boardCheck, int prevRow, int prevCol, int idx, int size) {
if (idx == size) return true;
int idx1 = idx+1;

bool found = false;
if (!found && prevRow+1 < row && board[prevRow+1][prevCol] == word[idx]) {
int point = (prevRow+1)*col+prevCol;
if (0 == boardCheck[point]) {
boardCheck[point] = 1;
found = find(board, row, col, word, boardCheck, prevRow+1, prevCol, idx1, size);
boardCheck[point] = 0;
}
}
if (!found && prevRow-1 >= 0  && board[prevRow-1][prevCol] == word[idx]) {
int point = (prevRow-1)*col+prevCol;
if (0 == boardCheck[point]) {
boardCheck[point] = 1;
found = find(board, row, col, word, boardCheck, prevRow-1, prevCol, idx1, size);
boardCheck[point] = 0;
}
}
if (!found && prevCol+1 < col && board[prevRow][prevCol+1] == word[idx]) {
int point = prevRow*col+prevCol+1;
if (0 == boardCheck[point]) {
boardCheck[point] = 1;
found = find(board, row, col, word, boardCheck, prevRow, prevCol+1, idx1, size);
boardCheck[point] = 0;
}
}
if (!found && prevCol-1 >= 0  && board[prevRow][prevCol-1] == word[idx]) {
int point = prevRow*col+prevCol-1;
if (0 == boardCheck[point]) {
boardCheck[point] = 1;
found = find(board, row, col, word, boardCheck, prevRow, prevCol-1, idx1, size);
boardCheck[point] = 0;
}
}

return found;
}
``````

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