This is one of those problems where the clean idea matters more than the amount of code. For 212. Word Search II, the solution in this repository is mainly a trie solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: trie, graph traversal, backtracking.
The notes already sitting in the source point us in the right direction:
- trie, dfs
- build trie from board, and then search with words(slow)
- TLE
- 32 / 36 test cases passed.
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are add, dfs, findWords.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//trie, dfs
02//build trie from board, and then search with words(slow)
03//TLE
04//32 / 36 test cases passed.
05class TrieNode{
06public:
07 vector<TrieNode*> children;
08
09 TrieNode(){
10 children = vector<TrieNode*>(26, nullptr);
11 }
12};
13
14class Trie{
15public:
16 TrieNode* root;
17
18 Trie(){
19 root = new TrieNode();
20 }
21
22 void add(string word){
23 TrieNode* cur = root;
24 for(char c : word){
25 if(cur->children[c-'a'] == nullptr){
26 cur->children[c-'a'] = new TrieNode();
27 }
28 cur = cur->children[c-'a'];
29 }
30 }
31
32 bool find(string word){
33 TrieNode* cur = root;
34 for(char c : word){
35 // cout << c << " ";
36 cur = cur->children[c-'a'];
37 if(cur == nullptr){
38 return false;
39 }
40 }
41 // cout << endl;
42
43 return true;
44 }
45};
46
47class Solution {
48public:
49 Trie* trie;
50 vector<vector<int>> dirs;
51
52
53 void dfs(vector<vector<char>>& board, int m, int n, vector<vector<bool>>& visited, int ci, int cj, string& str, int maxLen){
54 if(str.size() < maxLen){
55 // we won't build str whose size > maxLen
56 // cout << ci << ", " << cj << ", " << str.size() << endl;
57 //continue to build str
58 for(vector<int>& dir : dirs){
59 int ni = ci + dir[0];
60 int nj = cj + dir[1];
61
62 if(ni >= 0 && ni < m && nj >= 0 && nj < n && !visited[ni][nj]){
63 visited[ni][nj] = true;
64 str += board[ni][nj];
65 dfs(board, m, n, visited, ni, nj, str, maxLen);
66 visited[ni][nj] = false;
67 str.pop_back();
68 }
69 }
70 }
71
72 // cout << str << endl;
73 trie->add(str);
74 };
75
76 vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
77 int m = board.size();
78 if(m == 0) return vector<string>();
79 int n = board[0].size();
80
81 int maxLen = 0;
82 for(string& word : words){
83 maxLen = max(maxLen, (int)word.size());
84 }
85 // cout << "maxLen: " << maxLen << endl;
86
87 trie = new Trie();
88
89 dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};
90
91 string str;
92 vector<vector<bool>> visited(m, vector<bool>(n, false));
93
94 for(int i = 0; i < m; ++i){
95 for(int j = 0; j < n; ++j){
96 /*
97 process (ci, cj) before calling dfs,
98 is there a better way?
99 */
100 str = string(1, board[i][j]);
101 for(int tmp = 0; tmp < m; ++tmp){
102 fill(visited[tmp].begin(), visited[tmp].end(), false);
103 }
104 visited[i][j] = true;
105 dfs(board, m, n, visited, i, j, str, maxLen);
106 }
107 }
108
109 vector<string> ans;
110
111 for(string& word : words){
112 if(trie->find(word)){
113 ans.push_back(word);
114 }
115 }
116
117 return ans;
118 }
119};
120
121//trie, dfs
122//build trie from words, and then search with board
123//https://leetcode.com/problems/word-search-ii/discuss/59780/Java-15ms-Easiest-Solution-(100.00)
124//Runtime: 76 ms, faster than 81.82% of C++ online submissions for Word Search II.
125//Memory Usage: 38.4 MB, less than 42.23% of C++ online submissions for Word Search II.
126class TrieNode{
127public:
128 vector<TrieNode*> children;
129 string word;
130
131 TrieNode(){
132 children = vector<TrieNode*>(26, nullptr);
133 }
134};
135
136class Trie{
137public:
138 TrieNode* root;
139
140 Trie(){
141 root = new TrieNode();
142 }
143
144 void add(string word){
145 TrieNode* cur = root;
146 for(char c : word){
147 if(cur->children[c-'a'] == nullptr){
148 cur->children[c-'a'] = new TrieNode();
149 }
150 cur = cur->children[c-'a'];
151 }
152 /*
153 store the word at leaf,
154 so we don't need to reconstruct it
155 */
156 cur->word = word;
157 }
158
159 bool find(string word){
160 TrieNode* cur = root;
161 for(char c : word){
162 cur = cur->children[c-'a'];
163 if(cur == nullptr){
164 return false;
165 }
166 }
167
168 return true;
169 }
170};
171
172class Solution {
173public:
174 Trie* trie;
175
176 void dfs(vector<vector<char>>& board, int m, int n, int ci, int cj, TrieNode* node, vector<string>& ans){
177 //current building string "str" is replaced by "node"
178 //visited is replaced by '#'
179 char c = board[ci][cj];
180 //visited
181 if(c == '#') return;
182 //cannot find int trie
183 if(node->children[c-'a'] == nullptr) return;
184
185 node = node->children[c-'a'];
186 if(node->word != ""){
187 ans.push_back(node->word);
188 //de-duplicate
189 //so that it won't be found again
190 node->word = "";
191 }
192
193 //mark as visited
194 board[ci][cj] = '#';
195
196 if(ci > 0) dfs(board, m, n, ci-1, cj, node, ans);
197 if(ci+1 < m) dfs(board, m, n, ci+1, cj, node, ans);
198 if(cj > 0) dfs(board, m, n, ci, cj-1, node, ans);
199 if(cj+1 < n) dfs(board, m, n, ci, cj+1, node, ans);
200
201 board[ci][cj] = c;
202 };
203
204 vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
205 int m = board.size();
206 if(m == 0) return vector<string>();
207 int n = board[0].size();
208
209 trie = new Trie();
210
211 for(string& word : words){
212 trie->add(word);
213 }
214
215 vector<string> ans;
216
217 for(int i = 0; i < m; ++i){
218 for(int j = 0; j < n; ++j){
219 dfs(board, m, n, i, j, trie->root, ans);
220 }
221 }
222
223 return ans;
224 }
225};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.