• API
• FAQ
• Tools
• Archive
daily pastebin goal
60%
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));
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)
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.

Top