diff options
Diffstat (limited to 'other/word_search.cpp')
-rw-r--r-- | other/word_search.cpp | 53 |
1 files changed, 0 insertions, 53 deletions
diff --git a/other/word_search.cpp b/other/word_search.cpp deleted file mode 100644 index bbd072f..0000000 --- a/other/word_search.cpp +++ /dev/null @@ -1,53 +0,0 @@ -#include "leetcode.h" - -class Solution { -public: - bool exist(vvd(char) & board, string word) { - int dirs[5] = {0, -1, 0, 1, 0}; - map<char, int> cnt; - int m = board.size(), n = board[0].size(), l = word.size(); - - for (char c : word) - cnt[c] += 1; - - if (cnt[word[0]] > cnt[word[l - 1]]) - reverse(word.begin(), word.end()); - - function<bool(int, int, int)> dfs; - dfs = [&](int i, int j, int s) -> bool { - if (s == l) - return true; - - if (i < 0 or i >= m or j < 0 or j >= n) - return false; - if (board[i][j] != word[s]) - return false; - - board[i][j] = '#'; - for (int d = 0; d < 4; ++d) - if (dfs(i + dirs[d], j + dirs[d + 1], s + 1)) - return true; - board[i][j] = word[s]; - - return false; - }; - - for (int i = 0; i < m; ++i) - for (int j = 0; j < n; ++j) - if (dfs(i, j, 0)) - return true; - - return false; - } -}; - -int main() { - Solution obj; - vvd(char) board = { - {'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}; - string word = "ABCCED"; - if (obj.exist(board, word)) - cout << "true"; - else - cout << "false"; -} |