[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:    }  

[LeetCode] Two Sum, Solution

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

» Solve this problem

[Thoughts]
两种解法。
解法一， hash
从左往右扫描一遍，然后将数及坐标，存到map中。然后再扫描一遍即可。时间复杂度O(n)

解法二，双指针扫描
将数组排序，然后双指针从前后往中间扫描。时间复杂度O(n*lgn)。因为是要求返回原数组的下标，所以在排序的时候还得有额外的数组来存储下标信息， 也挺麻烦。

解法三，暴力搜索
这个倒是最省事的。时间复杂度O(n*n)

解法一实现如下：

1:    vector<int> twoSum(vector<int> &numbers, int target) {  
2:      map<int, int> mapping;  
3:      vector<int> result;  
4:      for(int i =0; i< numbers.size(); i++)  
5:      {  
6:        mapping[numbers[i]]=i;  
7:      }  
8:      for(int i =0; i< numbers.size(); i++)  
9:      {  
10:        int searched = target - numbers[i];  
11:        if(mapping.find(searched) != mapping.end())  
12:        {  
13:          result.push_back(i+1);  
14:          result.push_back(mapping[searched]+1);  
15:          break;  
16:        }  
17:      }  
18:      return result;  
19:    }  

解法二

1:       struct Node  
2:       {  
3:            int val;  
4:            int index;      
5:            Node(int pVal, int pIndex):val(pVal), index(pIndex){}  
6:       };  
7:       static bool compare(const Node &left, const Node &right)  
8:       {  
9:            return left.val < right.val;  
10:       }  
11:       vector<int> twoSum(vector<int> &numbers, int target) {  
12:            vector<Node> elements;  
13:            for(int i =0; i< numbers.size(); i++)  
14:            {  
15:                 elements.push_back(Node(numbers[i], i));  
16:            }  
17:            std::sort(elements.begin(), elements.end(), compare);  
18:            int start = 0, end = numbers.size()-1;  
19:            vector<int> result;  
20:            while(start < end)  
21:            {  
22:                 int sum = elements[start].val + elements[end].val;  
23:                 if(sum == target)  
24:                 {  
25:                      result.push_back(elements[start].index+1);  
26:                      if(elements[start].index < elements[end].index)  
27:                           result.push_back(elements[end].index+1);  
28:                      else  
29:                           result.insert(result.begin(),elements[end].index+1);  
30:                      break;  
31:                 }  
32:                 else if(sum > target)  
33:                      end--;  
34:                 else  
35:                      start++;                 
36:            }  
37:            return result;  
38:       }  

解法三，两个循环嵌套搜索，不写了。