[Leetcode] Palindrome Pairs, Solution

Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

Example 1:
Given words = ["bat", "tab", "cat"]
Return [[0, 1], [1, 0]]
The palindromes are ["battab", "tabbat"]

Example 2:
Given words = ["abcd", "dcba", "lls", "s", "sssll"]
Return [[0, 1], [1, 0], [3, 2], [2, 4]]
The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]

[Thoughts]

这题不难，找的是words[i] + words[j]是个palindrome。找两个例子就可以清晰的分析出规律来。

比如 “sssll”这个词，如果把这个词从中间切成两块， 就是 “ss” + “sll”。 ss本身就是palindrome，而“sll”的翻转就是字典里的“lls”

所以对于任意一个词，我们总是可以在其中任意一个位置K把它一切为二：

那么对于可能的candidate只有情况：

1. left 是 palindrome，那么可能的组合是 candidate | left | right，candidate就是right的翻转
2. right 是palindrome， 那么可能的组合是 left | right | candidate, 而这里candidate是left的翻转

所以，一开始有个hashmap，把翻转的字符串保存下来，这样在后面切字符串的时候，方便查询即可。

[Code]

1:    vector<vector<int>> palindromePairs(vector<string>& words) {  
2:      unordered_map<string, int> dict;  
3:      set<vector<int>> result;  
4:      for(int i =0; i< words.size(); i++) {  
5:        string word = words[i];  
6:        reverse(word.begin(), word.end());  
7:        dict[word] = i;  
8:      }  
9:      for(int i =0; i< words.size(); i++) {  
10:        string word = words[i];  
11:        // 切字符串三种情况，最左边切，中间切，和最右边切。   
12:        //注意，这里j<= word.size()为了cover最右边切这种情况  
13:        for(int j = 0; j<=word.size(); j++) {  
14:          string left = word.substr(0, j);  
15:          string right = word.substr(j, word.size() - j);  
16:          // candi | left | right  
17:          if(isPalindro(left) && dict.find(right) != dict.end() && dict[right] != i) {  
18:            result.insert({dict[right], i});  
19:          }  
20:          // left | right | candi  
21:          if(isPalindro(right) && dict.find(left) != dict.end() && dict[left] != i) {  
22:            result.insert({i, dict[left]});  
23:          }  
24:        }   
25:      }  
26:      std::vector<vector<int>> output(result.begin(), result.end());   
27:      return output;  
28:    }  
29:    bool isPalindro(string& str) {  
30:      int left = 0, right = str.size() -1;  
31:      while(left < right) {  
32:        if(str[left++] != str[right--]) return false;  
33:      }  
34:      return true;  
35:    }