leetcode

0 class Solution {

1 struct Node {

2 Node(){};

3 Node *children[27] = {nullptr};

4 bool &terminate = reinterpret_cast<bool &>(children[0]);

5

6 void insert(const string &s) {

7 Node *crnt = this;

8 for (const char c : s) {

9 const int idx = c & 0x1F;

10 if (!crnt->children[idx]) crnt->children[idx] = new Node();

11 crnt = crnt->children[idx];

12 }

13 crnt->terminate = true;

14 }

15 };

16

17 int n, m;

18 vector<string> res;

19

20 void dfs(vector<vector<char>> &board, Node *trie, int x, int y) {

21 const char c = board[x][y], idx = c & 0x1F;

22 if (c == '#' || !(trie = trie->children[idx])) return;

23

24 res.back().push_back(c);

25 if (trie->terminate) {

26 res.push_back(res.back());

27 trie->terminate = false;

28 }

29

30 board[x][y] = '#';

31 if (x > 0) dfs(board, trie, x - 1, y);

32 if (y > 0) dfs(board, trie, x, y - 1);

33 if (x < n) dfs(board, trie, x + 1, y);

34 if (y < m) dfs(board, trie, x, y + 1);

35 board[x][y] = c;

36 res.back().pop_back();

37 }

38

39 public:

40 vector<string> findWords(vector<vector<char>> &board, const vector<string> &words) {

41 Node *trie = new Node();

42 for (const string &word : words)

43 trie->insert(word);

44

45 n = board.size() - 1, m = board[0].size() - 1;

46

47 res.push_back("");

48 for (int i = 0; i <= n; i++) {

49 for (int j = 0; j <= m; j++) {

50 dfs(board, trie, i, j);

51 }

52 }

53 res.pop_back();

54

55 return res;

56 }

57 };