336. Palindrome Pairs

I tried brute force solution first, i.e. check if a new concatenated word is constructed before and if so we continue otherwise we need to check the new word and insert it into the hash table if it is a valid palindrome. This way runs O(n*n) time and can't pass large test set.

The one of top rated solution does a trick, i.e. it uses the reserve of word as the hash map key and the word's index as value. And the idea is for each word, scan from left to right, if left partition can be found in the hash map and the right partition is palindrome, then we'll find a palindrome, i.e.  "left partition | right partition | dict candidate". On the other hand, if right partition is found, then we find "candidate | left partition | right partition | ". There are some edge cases that need attention. I've added some comments in the code for the edge cases.

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> palindromePairs(vector<string>& words) {  
4:      unordered_map<string, int> dict;  
5:      vector<vector<int>> res;  
6:      for (int i = 0; i < words.size(); i++) {  
7:        string key = words[i];  
8:        reverse(key.begin(), key.end());  
9:        dict[key] = i;  
10:      }  
11:      for (int i = 0; i < words.size(); i++) {  
12:        for (int j = 0; j < words[i].size(); j++) {  
13:          string left = words[i].substr(0, j);  
14:          // words[i].size()-j > 0, which means this logic doesn't cover the case  
15:          // where right is empty, i.e. ""  
16:          string right = words[i].substr(j, words[i].size()-j);  
17:          // we need to kick out the case where words[i] itself is a palindrome  
18:          if (dict.find(left) != dict.end() && isPalindrome(right) && dict[left] != i) {  
19:            res.push_back({i, dict[left]});  
20:          }  
21:          if (dict.find(right) != dict.end() && isPalindrome(left) && dict[right] != i) {  
22:            res.push_back({dict[right], i});  
23:          }  
24:        }  
25:      }  
26:      // process the missing case above.  
27:      if (dict.find("") != dict.end()) {  
28:        for (int i = 0; i < words.size(); i++) {  
29:          if (isPalindrome(words[i]) && dict[""] != i) res.push_back({dict[""], i});  
30:        }  
31:      }  
32:      return res;  
33:    }  
34:    bool isPalindrome(string s) {  
35:      int l = 0, r = s.size()-1;  
36:      while (l < r) {  
37:        if (s[l++] != s[r--]) return false;  
38:      }  
39:      return true;  
40:    }  
41:  };  

Note, this problem involves searching word, then what data structure you can think of that is much faster than hash table? Yes, it is Trie. We can build trie tree for each reversed word just like what we did above inserting reversed word into hash map. And then we can follow the same idea to solve this problem.