This is one of those problems where the clean idea matters more than the amount of code. For 336. Palindrome Pairs, 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, two pointers, stack.
The notes already sitting in the source point us in the right direction:
- trie
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, isPalindrome.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- The stack stores unfinished context, which is usually the cleanest way to handle nested or monotonic structure.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- Substring checks are convenient but not free, so they are part of the real complexity story.
- 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
02//Runtime: 1144 ms, faster than 11.07% of C++ online submissions for Palindrome Pairs.
03//Memory Usage: 280.2 MB, less than 7.29% of C++ online submissions for Palindrome Pairs.
04class TrieNode{
05public:
06 vector<TrieNode*> children;
07 int index;
08 string word;
09
10 TrieNode(){
11 children = vector<TrieNode*>(26);
12 word = "";
13 index = -1;
14 }
15};
16
17class Trie{
18public:
19 TrieNode* root;
20
21 Trie(){
22 root = new TrieNode();
23 }
24
25 void add(string& word, int index){
26 TrieNode* cur = root;
27
28 for(char c : word){
29 if(cur->children[c-'a'] == nullptr){
30 cur->children[c-'a'] = new TrieNode();
31 }
32 cur = cur->children[c-'a'];
33 }
34 cur->word = word;
35 cur->index = index;
36 }
37
38 vector<TrieNode*> find(string& word){
39 //this function won't work for "word" which is empty
40 TrieNode* cur = root;
41 /*
42 if we want to find "sll",
43 both the trie node "s" and "sll" match
44 */
45 vector<TrieNode*> cands;
46
47 if(cur->index != -1 && cur->word != word){
48 //find for empty string
49 cands.push_back(cur);
50 }
51
52 for(int i = word.size()-1; i >= 0; --i){
53 char c = word[i];
54 if(cur->children[c-'a'] == nullptr){
55 /*
56 do not return {}!
57 because we may have found a leaf node previously!
58 */
59 // cout << "end finding" << endl;
60 return cands;
61 }
62 cur = cur->children[c-'a'];
63
64 // if((i == 0) && !(cur->index != -1 && cur->word != word)){
65 if(i == 0){
66 //reach the end of "word"
67 //put all leaves of "cur" into cands
68 //testcase: word: "a", and it want to find "ab"
69 stack<TrieNode*> stk;
70 stk.push(cur);
71
72 while(!stk.empty()){
73 cur = stk.top(); stk.pop();
74
75 if(cur->index != -1 && cur->word != word){
76 cands.push_back(cur);
77 }
78
79 for(TrieNode* child : cur->children){
80 if(child){
81 stk.push(child);
82 }
83 }
84 }
85 }else if(cur->index != -1 && cur->word != word){
86 //cur->index != -1: current node serves as a leaf
87 //cur->word != word: avoid finding itself!
88 // cout << "find " << cur->word << endl;
89 cands.push_back(cur);
90 }
91 }
92
93 return cands;
94 }
95};
96
97class Solution {
98public:
99 bool isPalindrome(string str){
100 int n = str.size();
101
102 for(int i = 0; i < n-1-i; ++i){
103 if(str[i] != str[n-1-i]){
104 return false;
105 }
106 }
107
108 return true;
109 };
110
111 vector<vector<int>> palindromePairs(vector<string>& words) {
112 Trie* trie = new Trie();
113 int n = words.size();
114
115 for(int i = 0; i < n; ++i){
116 trie->add(words[i], i);
117 }
118
119 vector<vector<int>> ans;
120
121 for(int i = 0; i < n; ++i){
122 // cout << "===" << words[i] << "===" << endl;
123 if(words[i] == ""){
124 for(int j = 0; j < n; ++j){
125 if(j == i) continue;
126 if(isPalindrome(words[j])){
127 // cout << "push: " << words[j] << endl;
128 ans.push_back({j, i});
129 }
130 }
131 }else{
132 vector<TrieNode*> cands = trie->find(words[i]);
133 if(cands.empty()) continue;
134
135 for(TrieNode* cand : cands){
136 int remainSize = words[i].size() - cand->word.size();
137 // cout << "cand: " << cand->word << ", remainSize: " << remainSize << endl;
138
139 if(remainSize == 0){
140 ans.push_back({cand->index, i});
141 }else if(remainSize > 0){
142 // cout << "check " << words[i].substr(0, remainSize) << " is palindrome? " << isPalindrome(words[i].substr(0, remainSize)) << endl;
143 if(isPalindrome(words[i].substr(0, remainSize))){
144 ans.push_back({cand->index, i});
145 }
146 }else{
147 //remainSize < 0
148 remainSize *= -1;
149 // cout << "check " << cand->word.substr(cand->word.size()-remainSize, remainSize) << " is palindrome? " << isPalindrome(cand->word.substr(cand->word.size()-remainSize, remainSize)) << endl;
150 if(isPalindrome(cand->word.substr(cand->word.size()-remainSize, remainSize))){
151 ans.push_back({cand->index, i});
152 }
153 }
154 }
155 // cout << endl;
156 }
157
158 }
159
160 return ans;
161 }
162};
163
164//trie, each node with a "palins" list
165//https://leetcode.com/problems/palindrome-pairs/discuss/79195/O(n-*-k2)-java-solution-with-Trie-structure
166//http://www.allenlipeng47.com/blog/index.php/2016/03/15/palindrome-pairs/
167//Runtime: 380 ms, faster than 74.84% of C++ online submissions for Palindrome Pairs.
168//Memory Usage: 269.4 MB, less than 10.56% of C++ online submissions for Palindrome Pairs.
169//time: O(n*k^2) for both building an searching
170class TrieNode{
171public:
172 vector<TrieNode*> children;
173 int index;
174 vector<int> palins;
175
176 TrieNode(){
177 children = vector<TrieNode*>(26);
178 index = -1;
179 }
180};
181
182class Trie{
183private:
184 TrieNode* root;
185
186 bool isPalindrome(string& str, int l, int r){
187 // cout << "check ";
188 // for(int i = l; i <= r; ++i){
189 // cout << str[i];
190 // }
191 // cout << endl;
192 for(; l < r; ++l, --r){
193 if(str[l] != str[r]){
194 return false;
195 }
196 }
197
198 return true;
199 };
200public:
201 Trie(){
202 root = new TrieNode();
203 }
204
205 void add(string& word, int index){
206 TrieNode* cur = root;
207
208 /*
209 insert into trie in reverse order,
210 then in "find",
211 we can search each char in positive order
212 */
213 for(int i = word.size()-1; i >= 0; --i){
214 /*
215 note: "cur" in now on the word[i+1]!
216 so we only have seen [i+1,n-1]!
217 */
218 // cout << "we are at " << word.substr(i+1) << endl;
219 if(isPalindrome(word, 0, i)){
220 /*
221 palins serves as a summary of a node's descendants
222 */
223 /*
224 we have seen word[i, n-1],
225 remaining word[0, i-1] needed to be check
226 */
227 cur->palins.push_back(index);
228 }
229 char c = word[i];
230 if(cur->children[c-'a'] == nullptr){
231 cur->children[c-'a'] = new TrieNode();
232 }
233 cur = cur->children[c-'a'];
234 }
235 cur->index = index;
236 //empty string is also a palindrome?
237 cur->palins.push_back(index);
238 }
239
240 void find(string& word, int index, vector<vector<int>>& res){
241 TrieNode* cur = root;
242
243 for(int i = 0; i < word.size(); ++i){
244 /*
245 note: "cur" in now on the word[i-1]!
246 so we only have seen [0,i-1]!
247 */
248 // cout << "we are at " << word.substr(0, i) << endl;
249 if(cur->index != -1 && cur->index != index && isPalindrome(word, i, word.size()-1)){
250 //cur->index != -1: current node serves as a leaf
251 //cur->index != index: avoid finding itself!
252 //isPalindrome(word, i+1, word.size()-1): word[i+1,n-1] is a palindrome
253 res.push_back({index, cur->index});
254 }
255
256 char c = word[i];
257
258 if(cur->children[c-'a'] == nullptr) return;
259
260 cur = cur->children[c-'a'];
261 }
262 //now we have finished the "word" to be searched
263
264 //but we haven't go to the leaf
265 for(int palinIndex : cur->palins){
266 if(palinIndex == index) continue;
267 res.push_back({index, palinIndex});
268 }
269 }
270};
271
272class Solution {
273public:
274 vector<vector<int>> palindromePairs(vector<string>& words) {
275 Trie* trie = new Trie();
276 int n = words.size();
277
278 for(int i = 0; i < n; ++i){
279 // cout << "===add " << words[i] << "===" << endl;
280 trie->add(words[i], i);
281 }
282
283 vector<vector<int>> res;
284
285 for(int i = 0; i < n; ++i){
286 // cout << "===find " << words[i] << "===" << endl;
287 trie->find(words[i], i, res);
288 }
289
290 return res;
291 }
292};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.