#include "leetcode.h" class Solution { public: bool exist(vvd(char) & board, string word) { int dirs[5] = {0, -1, 0, 1, 0}; map 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 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"; }