Description:
https://leetcode.com/problems/word-search/#/description
Algorithm:
main:
for each element in 2D vector
{
if (board[i][j] == word[0])
{
mark the element;
dfs(board, pos_x, pos_y, height, width, wordIdx, word);
unmark the element;
}
}
dfs:
if (wordIdx == word.size())if (wordIdx == word.size()) return true;
check the four surrounding letters
if (board[i][j] == word[0])
{
mark the element;
if dfs(board, pos_x, pos_y, height, width, wordIdx + 1, word)
return true;
unmark the element;
}
Code:
Actually my algorithm is TOTALLY the same with the fastest one. However, mine takes 76ms while the fastest only takes 6ms. I optimized my code again and again and finally get the fastest. Here are all my codes and i will show the improvements.
Code1 (76ms, beats 17.34%):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
class Solution { public: bool exist(vector<vector<char>>& board, string word) { if (board.size() == 0 || board[0].size() == 0 || word.size() == 0) return false; int m = board.size(); int n = board[0].size(); int result; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == word[0]) { board[i][j] = ~board[i][j]; if (searchNextLetter(board, i, j, 1, word)) return true; board[i][j] = ~board[i][j]; } } } return false; } private: bool searchNextLetter(vector<vector<char>> &board, int pos_x, int pos_y, int wordIdx, string word) { if (wordIdx == word.size()) return true; int m = board.size(); int n = board[0].size(); vector<vector<int>> direction = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} }; int newPos_x; int newPos_y; newPos_x = pos_x -1; newPos_y = pos_y; if (newPos_x >= 0 && board[newPos_x][newPos_y] == word[wordIdx]) { board[newPos_x][newPos_y] = ~board[newPos_x][newPos_y]; if (searchNextLetter(board, newPos_x, newPos_y, wordIdx + 1, word)) return true; board[newPos_x][newPos_y] = ~board[newPos_x][newPos_y]; } newPos_x = pos_x + 1; newPos_y = pos_y; if (newPos_x <= m - 1 && board[newPos_x][newPos_y] == word[wordIdx]) { board[newPos_x][newPos_y] = ~board[newPos_x][newPos_y]; if (searchNextLetter(board, newPos_x, newPos_y, wordIdx + 1, word)) return true; board[newPos_x][newPos_y] = ~board[newPos_x][newPos_y]; } newPos_x = pos_x; newPos_y = pos_y - 1; if (newPos_y >= 0 && board[newPos_x][newPos_y] == word[wordIdx]) { board[newPos_x][newPos_y] = ~board[newPos_x][newPos_y]; if (searchNextLetter(board, newPos_x, newPos_y, wordIdx + 1, word)) return true; board[newPos_x][newPos_y] = ~board[newPos_x][newPos_y]; } newPos_x = pos_x; newPos_y = pos_y + 1; if (newPos_y <= n - 1 && board[newPos_x][newPos_y] == word[wordIdx]) { board[newPos_x][newPos_y] = ~board[newPos_x][newPos_y]; if (searchNextLetter(board, newPos_x, newPos_y, wordIdx + 1, word)) return true; board[newPos_x][newPos_y] = ~board[newPos_x][newPos_y]; } return false; } }; |
Code2 (16ms, beats 64.74%):
Main change from Code1 to Code2 is the usage of newPos_x and newPos_y
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
class Solution { public: bool exist(vector<vector<char>>& board, string word) { if (board.size() == 0 || board[0].size() == 0 || word.size() == 0) return false; int m = board.size(); int n = board[0].size(); int result; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == word[0]) { board[i][j] = ~board[i][j]; if (searchNextLetter(board, i, j, 1, word)) return true; board[i][j] = ~board[i][j]; } } } return false; } private: bool searchNextLetter(vector<vector<char>> &board, int pos_x, int pos_y, int wordIdx, string word) { if (wordIdx == word.size()) return true; int m = board.size(); int n = board[0].size(); int newPos_x; int newPos_y; newPos_x = pos_x -1; if (newPos_x >= 0 && board[newPos_x][pos_y] == word[wordIdx]) { board[newPos_x][pos_y] = ~board[newPos_x][pos_y]; if (searchNextLetter(board, newPos_x, pos_y, wordIdx + 1, word)) return true; board[newPos_x][pos_y] = ~board[newPos_x][pos_y]; } newPos_x = pos_x + 1; if (newPos_x <= m - 1 && board[newPos_x][pos_y] == word[wordIdx]) { board[newPos_x][pos_y] = ~board[newPos_x][pos_y]; if (searchNextLetter(board, newPos_x, pos_y, wordIdx + 1, word)) return true; board[newPos_x][pos_y] = ~board[newPos_x][pos_y]; } newPos_y = pos_y - 1; if (newPos_y >= 0 && board[pos_x][newPos_y] == word[wordIdx]) { board[pos_x][newPos_y] = ~board[pos_x][newPos_y]; if (searchNextLetter(board, pos_x, newPos_y, wordIdx + 1, word)) return true; board[pos_x][newPos_y] = ~board[pos_x][newPos_y]; } newPos_y = pos_y + 1; if (newPos_y <= n - 1 && board[pos_x][newPos_y] == word[wordIdx]) { board[pos_x][newPos_y] = ~board[pos_x][newPos_y]; if (searchNextLetter(board, pos_x, newPos_y, wordIdx + 1, word)) return true; board[pos_x][newPos_y] = ~board[pos_x][newPos_y]; } return false; } }; |
Code3 (6ms, beats 99.61%):
Main change from Code2 to Code3 is to use string &word instead of string word.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
class Solution { public: bool exist(vector<vector>& board, string word) { if (word.size() == 0) return false; int m = board.size(); if (m == 0) return false; int n = board[0].size(); if (n == 0) return false; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == word[0]) { board[i][j] = ~board[i][j]; if (searchNextLetter(board, i, j, m, n, 1, word)) return true; board[i][j] = ~board[i][j]; } } } return false; } private: bool searchNextLetter(vector<vector> &board, int pos_x, int pos_y, int height, int width, int wordIdx, string &word) { if (wordIdx == word.size()) return true; if (pos_x - 1 >= 0 && board[pos_x - 1][pos_y] == word[wordIdx]) { board[pos_x - 1][pos_y] = ~board[pos_x - 1][pos_y]; if (searchNextLetter(board, pos_x - 1, pos_y, height, width, wordIdx + 1, word)) return true; board[pos_x - 1][pos_y] = ~board[pos_x - 1][pos_y]; } if (pos_x + 1 <= height - 1 && board[pos_x + 1][pos_y] == word[wordIdx]) { board[pos_x + 1][pos_y] = ~board[pos_x + 1][pos_y]; if (searchNextLetter(board, pos_x + 1, pos_y, height, width, wordIdx + 1, word)) return true; board[pos_x + 1][pos_y] = ~board[pos_x + 1][pos_y]; } if (pos_y - 1 >= 0 && board[pos_x][pos_y - 1] == word[wordIdx]) { board[pos_x][pos_y - 1] = ~board[pos_x][pos_y - 1]; if (searchNextLetter(board, pos_x, pos_y - 1, height, width, wordIdx + 1, word)) return true; board[pos_x][pos_y - 1] = ~board[pos_x][pos_y - 1]; } if (pos_y + 1 <= width - 1 && board[pos_x][pos_y + 1] == word[wordIdx]) { board[pos_x][pos_y + 1] = ~board[pos_x][pos_y + 1]; if (searchNextLetter(board, pos_x, pos_y + 1, height, width, wordIdx + 1, word)) return true; board[pos_x][pos_y + 1] = ~board[pos_x][pos_y + 1]; } return false; } }; |