daily pastebin goal
37%
SHARE
TWEET

Untitled

a guest Jan 21st, 2019 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     struct Trie {
  4.         array<shared_ptr<Trie>, 26> children;
  5.         int ind;
  6.         Trie(int i) : ind(i) {}
  7.     };
  8.     unordered_set<int> res;
  9.    
  10.     void addWord2Trie(const string& w, int i, int x, Trie* node) {
  11.         if (i >= w.size()) {
  12.             node->ind = x;
  13.             return;
  14.         }
  15.         if (!node->children[w[i]-'a'])
  16.             node->children[w[i]-'a'].reset(new Trie(-1));
  17.         addWord2Trie(w, i+1, x, node->children[w[i]-'a'].get());
  18.     }
  19.    
  20.     // to test that the word is in the trie
  21.     bool isWordInTree(const string& w, Trie* node) {
  22.         int i = 0;
  23.         while (i < w.size() && node->children[w[i] - 'a'] != nullptr) {
  24.             node = node->children[w[i] - 'a'].get();
  25.             ++i;
  26.         }
  27.         cout <<  w << " " << node->ind << " " << i << endl;
  28.         if (node->ind != -1 && i == w.size())
  29.             return true;
  30.         return false;
  31.     }
  32.    
  33.     void dfs(int i, int j, vector<vector<char>>& board, vector<vector<bool>>& visited, Trie* node) {
  34.         if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size())
  35.             return;
  36.         if (visited[i][j])
  37.             return;
  38.         Trie* next = node->children[ board[i][j]-'a' ].get();
  39.         visited[i][j] = true;
  40.         if (next) {
  41.             res.insert(next->ind);
  42.             dfs(i+1, j, board, visited, next);
  43.             dfs(i, j+1, board, visited, next);
  44.             dfs(i-1, j, board, visited, next);
  45.             dfs(i, j-1, board, visited, next);
  46.         }
  47.         visited[i][j] = false;
  48.     }
  49.    
  50.     vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
  51.         shared_ptr<Trie> trieRoot(new Trie(-1));
  52.         for (int x = 0; x < words.size(); ++x)
  53.             addWord2Trie(words[x], 0, x, trieRoot.get());
  54.         //for (int x = 0; x < words.size(); ++x)
  55.         //    cout << isWordInTree(words[x], trieRoot.get()) << endl;
  56.        
  57.         vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
  58.         for (int i = 0; i < board.size(); ++i)
  59.             for (int j = 0; j < board[i].size(); ++j) {
  60.                 for (int ii = 0; ii < board.size(); ++ii)
  61.                     for (int jj = 0; jj < board[0].size(); ++jj)
  62.                         visited[ii][jj] = false;
  63.                 dfs(i, j, board, visited, trieRoot.get());
  64.             }
  65.        
  66.         vector<string> r;
  67.         for (int i : res)
  68.             if (i != -1)
  69.                 r.push_back(words[i]);
  70.         return r;
  71.     }
  72. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top