各位大神能不能帮我看看Palindrome Pairs为什么会TLE(本地运行正确)

这道题有个很长的testcase （testcase附在下面  过不去，但是用leetcode run code 或者本地IDE跑都是能得到正确的结果的 (正确结果是 [] ) 。注意是不提交，只是点击leetcode的 "run code"按钮 也能得到这个结果。

实在是想不到哪里能有问题，唯一想到的是建trie的时候分配memory手动分配咋stack而不是heap上，这个方法当时在concatenate words的时候 看到discussion李提到过，但是我没看懂。。。（醉了）。。

我的思路就是分别建前缀树和后缀树。后缀树是每个单词的reverse。然后针对words中的每个单词，看这个单词是不是新组合单词的前缀（新组合单词的后缀就是从后缀树找到以但这个单词为前缀的所有单词）， or 看这个单词是不是新组合的后缀。

各位大大怎么看~~

1. #define CHILDSIZE 26
   
2. class TrieNode{
   
3. public:
   
4.     TrieNode * children[CHILDSIZE];
   
5.     bool isWord;
   
6.     TrieNode(): isWord(false){
   
7.         for (auto & child : children){
   
8.             child = nullptr;
   
9.         }
   
10.     }
    
11. };
    
12. 
    
13. class Trie{
    
14. public:
    
15.     TrieNode * root;
    
16.     Trie(){
    
17.         root = new TrieNode();
    
18.     }
    
19.     ~Trie(){
    
20.         for (int i = 0; i < CHILDSIZE; ++i){
    
21.             delete this->root->children[i];
    
22.         }
    
23.     }
    
24.     void insert(string word) {
    
25.         TrieNode * curr = root;
    
26.         for (int i = 0; i < word.size(); ++i){
    
27.             //每次判断这个节点是否存在,如果不存在则创建一个
    
28.             if (!curr->children[word[i]-'a']){
    
29.                 curr->children[word[i]-'a'] = new TrieNode();
    
30.             }
    
31.             curr = curr->children[word[i]-'a'];
    
32.         }
    
33.         curr->isWord = true; // 全部插完后加bool标记
    
34.     }
    
35. 
    
36.     bool startsWith(string prefix) {
    
37.         if (prefix.empty()){
    
38.             return false;
    
39.         }
    
40.         TrieNode * curr = root;
    
41.         for (int i = 0; i < prefix.size(); ++i){
    
42.             if (curr->children[prefix[i]-'a'] == nullptr){
    
43.                 return false;
    
44.             }
    
45.             curr = curr->children[prefix[i]-'a'];
    
46.         }
    
47.         //prefix每个字符都遍历完了
    
48.         return true;
    
49.     }
    
50.     // 我们已经假设prefix是trie树的合法前缀
    
51.     void findSuffix(vector<string> & res, string prefix){
    
52.         TrieNode * curr = root;
    
53.         for (int i = 0; i < prefix.size(); i++){
    
54.             if (curr->children[prefix[i]-'a']){
    
55.                 curr = curr->children[prefix[i]-'a'];
    
56.             }
    
57.         }
    
58.         string temp = "";
    
59.         for (int i = 0; i < CHILDSIZE; ++i){
    
60.             if (curr->children[i]){
    
61.                 TrieNode * preserved = curr;
    
62.                 curr = curr->children[i];
    
63.                 temp += ('a' + i);
    
64.                 if (curr->isWord){
    
65.                     res.push_back(prefix + temp);
    
66.                 }
    
67.                 findSuffix(res, prefix+temp);
    
68.                 temp.pop_back();
    
69.                 curr = preserved;
    
70.             }
    
71.         }
    
72.     }
    
73. };
    
74. 
    
75. class Solution {
    
76. public:
    
77.     vector<vector<int>> palindromePairs(vector<string>& words) {
    
78.         vector<vector<int>> res;
    
79.         unordered_map<string, int > wordsMap;
    
80.         if (words.empty()) return res;
    
81.         bool hasEmpty = false;
    
82. 
    
83.         // create trie
    
84.         Trie * prefixTrie = new Trie();
    
85.         for (int i = 0; i < words.size(); ++i){ // 正向的前缀树
    
86.             prefixTrie->insert(words[i]);
    
87.             wordsMap[words[i]]=i; // 构建前缀树的过程中 顺手把word:wordidx对应的map建好
    
88.             if (words[i] == ""){hasEmpty = true;} // 我们认为空字符串是任何单词的前缀 也是任何单词的后缀
    
89.         }
    
90.         Trie * suffixTrie = new Trie();
    
91.         for (string w : words){ // 反向的后缀树
    
92.             reverse(w.begin(), w.end());
    
93.             suffixTrie->insert(w);
    
94.         }
    
95.         // 查找
    
96.         for (int i = 0; i < words.size(); ++i){
    
97.             // 单词words[i]可能是新组合单词的前缀
    
98.             if (suffixTrie->startsWith(words[i])){ //如果在后缀树里
    
99.                 // 找到所有对应的单词
    
100.                 vector<string> alists;
     
101.                 suffixTrie->findSuffix(alists, words[i]); // 在后缀树中找到以words[i]为前缀的所有单词
     
102.                 alists.push_back(words[i]); // words[i]本身也可能是后缀树的组成部分
     
103.                 for (string wr : alists){
     
104.                     reverse(wr.begin(), wr.end());
     
105.                     string wcomb = words[i] + wr; // words[i]是新组合单词的前缀
     
106.                     if (wordsMap.count(wr) && isPalindrome(wcomb)){
     
107.                         int idx2 = wordsMap[wr];                     // 找对应的idx
     
108.                         if (i != idx2){ //distince [i,j]
     
109.                             res.push_back(vector<int>{i, idx2});
     
110.                         }
     
111.                     }
     
112.                 }
     
113. 
     
114.             }
     
115.             // 单词words[i]可能是新组合单词的后缀
     
116.             string wr = words[i];
     
117.             reverse(wr.begin(), wr.end());
     
118.             if (prefixTrie->startsWith(wr)){ // 如果在前缀树里
     
119.                 // 找到以reverse of words[i]为前缀的所有单词
     
120.                 vector<string> alists;
     
121.                 prefixTrie->findSuffix(alists, wr);
     
122.                 alists.push_back(wr); // words[i]本身是前缀树的一部分
     
123.                 for (string w : alists){
     
124.                     string wcomb = w + words[i]; // 注意这里不需要wr再reverse了！ words[i]是新组合单词的前缀
     
125.                     if (wordsMap.count(w) && isPalindrome(wcomb)){
     
126.                         int idx2 = wordsMap[w];                     // 找对应的idx
     
127.                         if (i != idx2){ //distince [i,j]
     
128.                             res.push_back(vector<int>{idx2, i});
     
129.                         }
     
130.                     }
     
131.                 }
     
132.             }
     
133.         }
     
134.         if (hasEmpty){
     
135.             int idx = wordsMap[""];
     
136.             for (int i = 0; i < words.size(); ++i){
     
137.                 if (i != idx && isPalindrome(words[i])){
     
138.                     res.push_back(vector<int>{i,idx}); // 空字符是任何单词（如果单词本身是回文串）的后缀
     
139.                     res.push_back(vector<int>{idx, i}); // 空字符是任何单词（如果单词本身是回文串）的前缀
     
140.                 }
     
141.             }
     
142.         }
     
143.         std::sort(res.begin(), res.end());
     
144.         res.erase(std::unique(res.begin(), res.end()), res.end());
     
145.         return res;
     
146.     }
     
147.     // 检查单词是不是palindrome
     
148.     bool isPalindrome(string &s){
     
149.         if (s.empty()){return true;}
     
150.         if (s.size() <= 1){ return true;}
     
151.         int left = 0, right = (int)(s.size()-1);
     
152.         while (left < right){
     
153.             if (s[left] == s[right]){
     
154.                 left++; right--;
     
155.             }
     
156.             else{ return false; }
     
157.         }
     
158.         return true;
     
159.     }
     
160. };
     
161. 
     
162. int main(){
     
163.     vector<string> words = {"aba","ba","a","caba"};
     
164.     vector<vector<int> > pairs = Solution().palindromePairs(words);
     
165.     for (auto p: pairs){
     
166.         for (auto i : p){
     
167.             cout << i << " ";
     
168.         }
     
169.         cout << endl;
     
170.     }
     
171.     return 0;
     
172. }

复制代码

最长的那个test case： {"bbaabaaaabbbbaaaabaaaabaabbabbbaaabbabbbabbaaababbaabbaaaabbbaabbaabaaaabaaabbaabab","babbbbbaabbbaaaaaabbbbbbbaabbabbabbbbbaababaabbabbbabbbbbbabba","bbbbaabbbababbabbbbabaababaabbaabbabaaaaabababbabbabbbbbabbbbaaaabbabbabbbabababbbaaa","ababbbbbbbaaaabbaaababbbabababbaabbaababbbabbbabaabbaabaababbbabababaaabbbbabbaa","abbbaababaaaaabababaabaaaaaabbbbbbbababaaaabaabbbaaabbaaaabbbabbbbabbaaaaaaaaaaabbaaaababbabbbabbabaaaaabbaababbabbabababaaaaabbabbababbaaaabbbababaaabbaaabbabbaaba","aabbaaaaaaabaaabbbababbbbabababaaabbbabaabbababbaabbbbbaabbbbaabaa","abbabaabbaaaaaababbbabbabababbababbbbaaaaabbbaaabbaababbababbbabbaaaabbabbbabbabaaaaaaabbabbbaababaaaabbaabaabababbaaaababbabbbabaabbabbbbaaaabbabbaabbaaaababbbbbbaaaaaababba","abbabaabbabbabbbabaabbbbbabaabbbbaabaaabaabaaabbaaaaaaababbababb","bbabbbbaaabbbbaaababbabaabbbbababaaaabbaaabbbaabbbaaabaababababaaaaabbbbaaaabbbababbabbbbaabbbbaaaaaaaaaabbabaaabaabaaa","aabaabbabbabbaaabbbbbaabbaababbabbaabbabaaaaaababaabaabbaaaabbabbbaababaaabaabbbbbaabbbbabbbbaaaaabbbbabbbbabaabaabbaabbbabaabababaabbaaaaabbabaaabbaabbbabaaaababbabbbababaaabbaa","bbbaaaaaaaabaababbabbabbbb","aabbaababbbbbbbabbbababaaaababbabaaabbaaaaabbbaaababbaaabbaaaaaaabbaabbaababbbbaabbaababbabbbbbbaaabaaaabbaabaababaabaab","aabbaabaabbabaabbbababbbaababbaaaababaaaaabaaaababbabbabababaaaabbabbbabbbbbbaababaaabbbababaabaaaabbbabaaa","aabbbbbbaabbabababbbbabbbbbaabbabaabbaaabbbb","ababbabaaabaaa","babbaaaaabbaaabaaaabaabaabaaabaaaaaaabaaabba","bababaabbaaaaababbabaaabbbabababbbbbabbbbababb","aaababbbbaabaabaaaabaabbabbababaaaaab","baabbbbbaabbaaaaababbabaabbabaaaabbabbbaabbabababababbaabaaabbbaabaabbbabbaaabbbbabababaabaabaabaabbbaaabaaabbbaaabaaaabbaaabbaaaababbbbabbaabbababbaabbbbbbababaaaabbbababa","baabbabaabaababbbaababbbbbabbbabbaaaaaaaabbbaabbaabaabbbabaabaabaabbaaabaaaabaaabaababaa","bbabbbabaababaabaaabbbbaaaaaabbbaaaaaaabababababbbbababbaaaaabbaabbabababbaaaabababbababbabbababbabbaa","aabbaabaabbaaabaaaaaabaaabbabababaaaabbabaabaaabbbabababbaabaaabbabbbbabbaabbababbbabbaaaabaaababbabbbbbbaaabbaababbabaabaaabaaabbbabaababaa","babaaababaabbabbabbbbbabaaabbaaabbabaabbabbabbbaabbbaaaaaabaabbaababbbbaaababbababbabbbabaababaabbabababbbabaabbbbaabaababbaa","bbabbababaaababababaabaaaaaaaabaababaababbabbabb","bbabbbbabbaaaabaabbbbbbabbbaaaaaaabbbbabbaaabbabaabbabaabbbbbbaabbbabaaabbabaaabbaba","baabbbbbbaaaaabbaabbbbabaaabbaaaabbbaaabbabaaababaababbbbbbabbaabaaabaaabbabbabaaaba","bbbaabaabbabababbaaabbaaaababaabbbbaabaaaaaaaaabbbbaabbbbabbbabababbabbbbababbaabbba","aabbbaabaababaaaabbbbabaabaabaaabababbaabbaabbaaabaababaaabbbabaaababaabbaababbbbaababaabaabbaababbababbbbbababababaabbabbaabaaaaaabaabbaabaabaaabaabba","abbabaababbbbbbaaaaaababbaabaabbaabbaaaababaababaabbbbbaaaabbbabbbbbaabbbbbbaaababbbaabaabababb","bbbaabaabaaaaabaabaabbbbaaaabaabbbbbaabbaaabbbbbababbbbabbaaaaabbaababababababbbbbbbaaabaabbbaaaaababbbaabbabaabababbbbaaabaabbababbbaabbaabbbbaaaabababbabaabbaaaaaababaaaaabaababaabbabaabbabababab","babaabaabaabbbabaaaabaabbbaaaaaaabaababbabbbaabbbabaababbabbaabbaaabaaaabaababbabbaababbabababbbabaabbbababbbbbbbaaababbaaaabaabaabbababbaaabbaabbbaaabaabaaaabaa","abbbababaaabbaabbbbabababbaabbaaaabaabaabbbbbbbbaabbbbaaaaabbbbabaaaaabbbaaaaabbbbaaaaaababbbbbaabbabaaaaabbaabaaabaababbabaabaaabbab","babaabaababababbbbabababbbaabbaaabbbaabbaaaabaaabbbbbaaaab","aaaabbaabababbbaa","bbbbabbaabaabbbbaaaaaaaabbaababaaabaaabaaabbbbaababbbaabaabbbbaaabbabaabbbbbabbbbaaabababaabbaaababbabababbbabbabaabaaaabbab","aababaabaaaaaabbabababaaaaababbbbaabaa","bbababaaaaaaaaabaabbaaaabaaaaaaaaabbbabaabbbbbabaabaaabbbabbbabbbaaaaaabaaabbbbbbaa","abbaabaaaaabbaaaaaabbbbabaabbabbaabbbabbababaabaabaaabbababbaaabaababbbbbabbbabbabbaaaabbaababbaababbbabbbbbbaaabbbbbbb","baabababbbbbaabbbabaababaababaababbbabbbbbababbaababbaaaabaaabbbbaaaababbabbbabaabaabbababaaa","abbaabbbaabbabbabbbbbbbabbbabbaaabbaaababbaabbaababab","bbabbabbbbbbabababbbabaabbbaaaabababbaabbbabbbbaababbaabaaabbbbabaaaabbbabbaaabaabbaabbbaaababbaaaabaabbabbbabbbaaabaaabbbbabbaabbaabaa","aaaabbbabbaabbababbabbabaababbababaabbaaabaaaababbbabbaaaabbbbabaaabbbaaabababbbabbaabaaabbaabbbaabbbbaaabbbaabbbbababaaaaababbbabaabbbbbbabbabbbbbabaaabaaaaaabbaa","babaaabaabbaababaaabbaaababbbbbbbaabbbbbbbbabbaabbbbbbaaaaabbaabababaabbbabaaaaaaabbaabababaaabbabbabbaababbaaabbbaaaababbbbbabbbaabbbaaaabbabbaabbbaababbaaaabbaaaababbbbbb","abaababbaaabbbaaaaababaabbab","aabbaaaababbbabbbaaabaabababbabbbaabaaaabaabaaaabbabaabbaaabbbaaabbaabbabbbbaaabbbababbaabbaaaabbbabaabbbabbbbbbbaab","aabbbabbabaaaaabbabbababbbabbbbbbbbaabbbbabbbaabaabbaaababbbaaaaabbaaabbab","baaaabababaaababbaabbbabaaabbbbabbbbaaaabbabbbbbbbbababbaaaaabaabaaabbaabbbbbabababaabbbbaabbbbbabbaabaaabaababbbabbbabaababbaaaabbaaaaaabaababbbabaabbbaaabbbabbbaabbbbbbaabbabbbbabaabbbbaba","bbbaababaabaabbabbaabbabbaabbbbabaabbabbbbbbbabbaaaaababaaabbbaba","baaaaababaabaabaabbbbabbbbbaabbaabbaaababaabaababaabbaaabbabbbabbbaababababbaaaab","baabaaababbabbbaaaabbaabbaababbaababbbaabaabaaaaaabbbbababaaabaaabaababbaabbabbaababbbbbabbabbaabbaabbbabbbaabb","bbaaaaabbbaaabbbaaaaaaaaaabaaaaa","bbbbbbabaaaaabbbbaaabbabaababaabababbabbabaabababababbaabbabbbabbbababa","bbaabbbaabbabababaaaaaabbaabbababbbbabaabbbaabbabaabbbabbbabbaaabbabbababaaabbbababbabbbbbbbbaaaaabbaa","abaabbbaabbbbaabbabaabaaabaabaaaabbabbbabbaaabbbbababaabaaabaaaaaaaabaaaababbababaabbbbbaababaabbbbabbaaabbbabbabbbbabbbbaabaaa","bababbabbaaabbabaababbbbaabaabbbbbbababaabbbbaababababbaabbaabaaaababbabbabab","baaabbabbaaababbbbbbbaabaaabbabbaaabbabababbaaaabaabbbbaaaabbabbbbbbabaaaaabaabaaaaabababbbaabbaabbabbbbbabaababababbbbbbaabbbabbbaaabaabababaabaabbbbbbbbabaaaaabbaababab","ababababababbbabbabbbbbabbabbbbabbaaabbbbbbbbbbabbaabaabbbababbabbbaaaababbaabbbaab","baaaabbababbabaabbabbaabbbbabbbabbabbbbbabaaaabaabbbabbaababbabababaaaaabaaaababbbabbbaaaaabbbabbbaaaabbbbbaaaba","baababbbaaaabbbaaababbabaababbbbbaaabaabaaabababbbbaabbaaabaaabaaaaaabbbbbaabaaaababbbaabb","aaabaabbabaaaaaaaaaabbb","abbbaabaabbbbbabbaababbaaaaababbaaaaabbabbbb","ababaabababbbabbbbaaabbabbbaaaaaaabbabbbaba","baababbaabbbaabbbbbbaaabbbbaaaabbbbabaabbaaabaaababbbaaabbaabaabaabaaabbbbbaabaaaaab","babbabababaabbbaabababaaaaaaaaaabbbbabbababbbaaaabbaabababbbbbbbababaaaababbaaaabaabaaabaabaaaaababbbbababbaabbaaabbabaaababbbbbabbbaaabaababbaabbabbbbaaaabababaaa","abbbbbaaaaabbaabbbabaabbabaabbbaaabbaaabaabbb","abbababb","aababaaabbbabbbbaaaabaababbababbbaaaaabbababbbbaaaaaababababaabaaaabbbabbaababbbabbabaabbababbbbabbabbbabaaabababaababbbbbaaabaabaaaabbabbaaababbabaaaaa","abbbaaaaabaabbbabbbabbaaabbaababababbbaabbababaababaabbaaababbabbb","aaabaaabaabaababbabbbbaaaaaaaaabbbabbaabbababbaabababbbbbabbabababbabaaaabbbbabbbbbbbabbabaabababbaaabbaaaaaabbababbbbbbbaabbabbaaaababbabaaabbaabaaababaabaaaabaaba","baabbabbaabbbabbbbabbbaabbabaababaaaabaaaabbaaabaaababbabbbbbabaabbbaababaaababaababbaabaabaabababaaabbbbaabbbabbbbbba","abaababaaabaabbaabaaababbaabbbababbbaaaaaabbbabaaababbaabbbbaaabaabbaaabaaaababbabbbbbababbbaabbaaababaaaaaaababbbbbba","aaaabbaaaaaabbbaaaaabbaabbaabaabbababbbbbabababbababbabbaaaaabbaaabbabbaaabbbbbbaaabbbbbabbbbbabbabbaaaaaabbbbbaaaaaabbabbbbbbabbbaabbbaababbbbbabbaaabaa","ababbaaaababababbabaaabaaaaaabbbbababaababbababaabaabababaaaabbaaabaaaaaaabbbbababbabbbbabbbbbbabbbabaabbbabbbbbabbbbbababbbbaabbbaabbbababaaaabbbbaaabbab","bbabaababbabbbbbbaabbaaaabbaaabbabbaaabbabbaabaaabbbabbbababaabbbaaba","bbaaabbbaabaababbbababaaabbbbababbbbbaabaaabbbaabbbaaaaabbaabbaabaaabbabaababaaabbaababaabbbbbbaaabbabaabababaabbbaaaaabbbaaaabaabbababaaababaabbaabaaaaabaaaababbabaabababababaabaaaabaaabbaaabbbbababa","abbaaabbbaabbabb","abbbabbaaaabaabaaababaaaaabababbbaabbbbaabbbaaa","babaaabbbbbb","baaabaaabbbabaabbbaabaabbaaaabbbabbabbbbbaabbabbbabaabababaabbbbabaabaabbaaabbbabaaaaaaaaaabbbbaaabbaaaaaabaababbaabbabaabbbabaaabbbbaabbaababba","babababbbbabbaaaaaabbbbbaba","babba","abbbabaabbabbbbbbbbababaaaaaab","bbabbabbbabaaabbbaaababbbbaaaaaaabab","bbabbaabbbabaaaaaababaabbbabaaabaaababaabaaaaaaaaaaabbaababaababbababbabbababbbaaabbaaaabbaabbbbaaabbabbbabaabbbbbabababbaabaabbbabaabaaabaaababbbabbabbaababaabbbbaabaabbabbbbabbabbaababbbbba","bbaaabaaababaaaabbaabbabbbaabbaaabaababbaaababbbaaabaabaabbabababaaaabbbbbaaaabbbbbbababbbbabbbababbaababaababbbabaaabbabaaaabababaaabababaaabbbbbaaaaababaabbbbaabaaabba","ababaaaaaabbabbabba","aaabababaabaaabaaaaabaaabaababbbbbababbbabbbbbbaabbaaaaaba","baabbbab","abbaaaaababbbaaaabbbaaabbaaababbababababaabbabaabaaabaabaaabbaaabbababbaabaaaabaabababbbbbbabaabaaabaaaababbaababbaabbbbbaabbbbbbabaa","ababaaabbababbabbbaabbbaabaaaaaaaabbabaabaaaaaabaa"}

然后再给lz贴个我当时的做法。我刷的时候是抱着面试必须能写出来的思想做的(interview-friendly code)，所以代码尽量简单。面试用Trie这个真心费时间（虽然我面FB时不得已也用了），所以尽量用简单好实现的做法。
我这个做法和Top voted那几个有些类似，但代码比他们短，运行速度比他们快很多（我是99%，他们在60%左右）， 权当参考。

1. class Solution {
   
2.     bool isPalindrome(const string & word, int start, int end)
   
3.     {
   
4.         for (int i = 0; i < (end - start)/2; ++i)
   
5.             if (word[start + i] != word[end - i - 1])
   
6.                 return false;
   
7.         return true;
   
8.     }
   
9. public:
   
10.     vector<vector<int>> palindromePairs(vector<string>& words)
    
11.     {
    
12.         unordered_map<string, int> dict;
    
13.         for (int i = 0; i < words.size(); ++i)
    
14.             dict[words[i]] = i;
    
15.         vector<vector<int>> results;
    
16.         for (int i = 0; i < words.size(); ++i)
    
17.         {
    
18.             string temp = words[i];
    
19.             reverse(temp.begin(), temp.end());
    
20.             auto iter = dict.find(temp);
    
21.             if (temp != words[i] && iter != dict.end())
    
22.                 results.push_back(vector<int>{iter->second, i});
    
23.             for (int j = 1; j <= words[i].size(); ++j)
    
24.             {
    
25.                 if (isPalindrome(words[i], 0, j))
    
26.                 {
    
27.                     string temp = words[i].substr(j, words[i].size() - j);
    
28.                     reverse(temp.begin(), temp.end());
    
29.                     auto iter = dict.find(temp);
    
30.                     if (iter != dict.end())
    
31.                         results.push_back(vector<int>{iter->second, i});
    
32.                 }
    
33.                 if (isPalindrome(words[i], words[i].size() - j, words[i].size()))
    
34.                 {
    
35.                     string temp = words[i].substr(0, words[i].size() - j);
    
36.                     reverse(temp.begin(), temp.end());
    
37.                     auto iter = dict.find(temp);
    
38.                     if (iter != dict.end())
    
39.                         results.push_back(vector<int>{i, iter->second});
    
40.                 }
    
41.             }
    
42.         }
    
43.         return results;
    
44.     }
    
45. };

复制代码

LZ太实诚了，我开玩笑的要了大米，LZ真的给了！！！
无功不受禄，看了LZ的求助贴，帮LZ改了下，现在可以Pass了。

LZ原来code有两处内存泄漏，我改了3 lines，分别是(改后代码里的）：12,28,151。我打了感叹号的位置，应该比较醒目。原因写在inline了。lz要是不明白继续追问即可。

1. #define CHILDSIZE 26
   
2. class TrieNode{
   
3. public:
   
4.     TrieNode * children[CHILDSIZE];
   
5.     bool isWord;
   
6.     TrieNode(): isWord(false){
   
7.         for (auto & child : children){
   
8.             child = nullptr;
   
9.         }
   
10.     }
    
11. 
    
12.     //！！！！添加TrieNode的析构，这个析构会级联（DFS）析构所有子节点。原因见下条。
    
13.     ~TrieNode()
    
14.     {
    
15.         for (int i = 0; i < CHILDSIZE; ++i){
    
16.             delete children[i];
    
17.         }
    
18.     }
    
19. };
    
20. 
    
21. class Trie{
    
22. public:
    
23.     TrieNode * root;
    
24.     Trie(){
    
25.         root = new TrieNode();
    
26.     }
    
27.     ~Trie(){
    
28.         delete root; //！！！！ 你原来的写法只会delete root的第一层children，可是他们也有children啊，你只杀了他们的爹而不杀他们，那这些grandchildren就变成orphan了。 所以这里delete root就好，级联DFS delete在TrieNode析构实现。
    
29.     }
    
30.     void insert(string word) {
    
31.         TrieNode * curr = root;
    
32.         for (int i = 0; i < word.size(); ++i){
    
33.             //每次判断这个节点是否存在,如果不存在则创建一个
    
34.             if (!curr->children[word[i]-'a']){
    
35.                 curr->children[word[i]-'a'] = new TrieNode();
    
36.             }
    
37.             curr = curr->children[word[i]-'a'];
    
38.         }
    
39.         curr->isWord = true; // 全部插完后加bool标记
    
40.     }
    
41. 
    
42.     bool startsWith(string prefix) {
    
43.         if (prefix.empty()){
    
44.             return false;
    
45.         }
    
46.         TrieNode * curr = root;
    
47.         for (int i = 0; i < prefix.size(); ++i){
    
48.             if (curr->children[prefix[i]-'a'] == nullptr){
    
49.                 return false;
    
50.             }
    
51.             curr = curr->children[prefix[i]-'a'];
    
52.         }
    
53.         //prefix每个字符都遍历完了
    
54.         return true;
    
55.     }
    
56.     // 我们已经假设prefix是trie树的合法前缀
    
57.     void findSuffix(vector<string> & res, string prefix){
    
58.         TrieNode * curr = root;
    
59.         for (int i = 0; i < prefix.size(); i++){
    
60.             if (curr->children[prefix[i]-'a']){
    
61.                 curr = curr->children[prefix[i]-'a'];
    
62.             }
    
63.         }
    
64.         string temp = "";
    
65.         for (int i = 0; i < CHILDSIZE; ++i){
    
66.             if (curr->children[i]){
    
67.                 TrieNode * preserved = curr;
    
68.                 curr = curr->children[i];
    
69.                 temp += ('a' + i);
    
70.                 if (curr->isWord){
    
71.                     res.push_back(prefix + temp);
    
72.                 }
    
73.                 findSuffix(res, prefix+temp);
    
74.                 temp.pop_back();
    
75.                 curr = preserved;
    
76.             }
    
77.         }
    
78.     }
    
79. };
    
80. 
    
81. class Solution {
    
82. public:
    
83.     vector<vector<int>> palindromePairs(vector<string>& words) {
    
84.         vector<vector<int>> res;
    
85.         unordered_map<string, int > wordsMap;
    
86.         if (words.empty()) return res;
    
87.         bool hasEmpty = false;
    
88. 
    
89.         // create trie
    
90.         Trie * prefixTrie = new Trie();
    
91.         for (int i = 0; i < words.size(); ++i){ // 正向的前缀树
    
92.             prefixTrie->insert(words[i]);
    
93.             wordsMap[words[i]]=i; // 构建前缀树的过程中 顺手把word:wordidx对应的map建好
    
94.             if (words[i] == ""){hasEmpty = true;} // 我们认为空字符串是任何单词的前缀 也是任何单词的后缀
    
95.         }
    
96.         Trie * suffixTrie = new Trie();
    
97.         for (string w : words){ // 反向的后缀树
    
98.             reverse(w.begin(), w.end());
    
99.             suffixTrie->insert(w);
    
100.         }
     
101.         // 查找
     
102.         for (int i = 0; i < words.size(); ++i){
     
103.             // 单词words[i]可能是新组合单词的前缀
     
104.             if (suffixTrie->startsWith(words[i])){ //如果在后缀树里
     
105.                 // 找到所有对应的单词
     
106.                 vector<string> alists;
     
107.                 suffixTrie->findSuffix(alists, words[i]); // 在后缀树中找到以words[i]为前缀的所有单词
     
108.                 alists.push_back(words[i]); // words[i]本身也可能是后缀树的组成部分
     
109.                 for (string wr : alists){
     
110.                     reverse(wr.begin(), wr.end());
     
111.                     string wcomb = words[i] + wr; // words[i]是新组合单词的前缀
     
112.                     if (wordsMap.count(wr) && isPalindrome(wcomb)){
     
113.                         int idx2 = wordsMap[wr];                     // 找对应的idx
     
114.                         if (i != idx2){ //distince [i,j]
     
115.                             res.push_back(vector<int>{i, idx2});
     
116.                         }
     
117.                     }
     
118.                 }
     
119. 
     
120.             }
     
121.             // 单词words[i]可能是新组合单词的后缀
     
122.             string wr = words[i];
     
123.             reverse(wr.begin(), wr.end());
     
124.             if (prefixTrie->startsWith(wr)){ // 如果在前缀树里
     
125.                 // 找到以reverse of words[i]为前缀的所有单词
     
126.                 vector<string> alists;
     
127.                 prefixTrie->findSuffix(alists, wr);
     
128.                 alists.push_back(wr); // words[i]本身是前缀树的一部分
     
129.                 for (string w : alists){
     
130.                     string wcomb = w + words[i]; // 注意这里不需要wr再reverse了！ words[i]是新组合单词的前缀
     
131.                     if (wordsMap.count(w) && isPalindrome(wcomb)){
     
132.                         int idx2 = wordsMap[w];                     // 找对应的idx
     
133.                         if (i != idx2){ //distince [i,j]
     
134.                             res.push_back(vector<int>{idx2, i});
     
135.                         }
     
136.                     }
     
137.                 }
     
138.             }
     
139.         }
     
140.         if (hasEmpty){
     
141.             int idx = wordsMap[""];
     
142.             for (int i = 0; i < words.size(); ++i){
     
143.                 if (i != idx && isPalindrome(words[i])){
     
144.                     res.push_back(vector<int>{i,idx}); // 空字符是任何单词（如果单词本身是回文串）的后缀
     
145.                     res.push_back(vector<int>{idx, i}); // 空字符是任何单词（如果单词本身是回文串）的前缀
     
146.                 }
     
147.             }
     
148.         }
     
149.         std::sort(res.begin(), res.end());
     
150.         res.erase(std::unique(res.begin(), res.end()), res.end());
     
151.         delete prefixTrie, suffixTrie; //！！！！ C++不会自己delete pointer的，自己要手动delete。
     
152.         return res;
     
153.     }
     
154.     // 检查单词是不是palindrome
     
155.     bool isPalindrome(string &s){
     
156.         if (s.empty()){return true;}
     
157.         if (s.size() <= 1){ return true;}
     
158.         int left = 0, right = (int)(s.size()-1);
     
159.         while (left < right){
     
160.             if (s[left] == s[right]){
     
161.                 left++; right--;
     
162.             }
     
163.             else{ return false; }
     
164.         }
     
165.         return true;
     
166.     }
     
167. };
     
168. 
     

复制代码

感谢前辈的指点！ 闷头想了一天，也没有您指点之后领悟的快！ 谢谢！

fentoyal 发表于 2017-8-11 09:37
然后再给lz贴个我当时的做法。我刷的时候是抱着面试必须能写出来的思想做的(interview-friendly code)，所 ...

从前辈这里学到一个非常有用的面试tip就是写题目一定要知道一种"interview-friendly code"的解法。 比如这道题用trie做，洋洋洒洒150行，很容易就有bug而且还找不到。。。