nikunjsoni

212

Jun 26th, 2021
100
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.     struct TrieNode {
  3.         TrieNode *children[26];
  4.         string word;
  5.  
  6.         TrieNode() : word("") {
  7.             for (int i = 0; i < 26; i++) {
  8.                 children[i] = nullptr;
  9.             }
  10.         }
  11.     };
  12.  
  13. public:
  14.     vector<string> findWords(vector<vector<char>> &board, vector<string> &words) {
  15.         TrieNode *root = buildTrie(words);
  16.         vector<string> result;
  17.         for (int i = 0; i < board.size(); i++) {
  18.             for (int j = 0; j < board[0].size(); j++) {
  19.                 dfs(board, i, j, root, result);
  20.             }
  21.         }
  22.         return result;
  23.     }
  24.  
  25.     /** Inserts a word into the trie. */
  26.     TrieNode *buildTrie(vector<string> &words) {
  27.         TrieNode *root = new TrieNode();
  28.         for (int j = 0; j < words.size(); j++) {
  29.             string word = words[j];
  30.             TrieNode *curr = root;
  31.             for (int i = 0; i < word.length(); i++) {
  32.                 char c = word[i] - 'a';
  33.                 if (curr->children[c] == nullptr) {
  34.                     curr->children[c] = new TrieNode();
  35.                 }
  36.                 curr = curr->children[c];
  37.             }
  38.             curr->word = word;
  39.         }
  40.         return root;
  41.     }
  42.  
  43.     void dfs(vector<vector<char>> &board, int i, int j, TrieNode *p, vector<string> &result) {
  44.         char c = board[i][j];
  45.         if (c == '#' || !p->children[c - 'a']) return;
  46.         p = p->children[c - 'a'];
  47.         if (p->word.size() > 0) {
  48.             result.push_back(p->word);
  49.             p->word = "";
  50.         }
  51.  
  52.         board[i][j] = '#';
  53.         if (i > 0) dfs(board, i - 1, j, p, result);
  54.         if (j > 0) dfs(board, i, j - 1, p, result);
  55.         if (i < board.size() - 1) dfs(board, i + 1, j, p, result);
  56.         if (j < board[0].size() - 1) dfs(board, i, j + 1, p, result);
  57.         board[i][j] = c;
  58.     }
  59. };
RAW Paste Data