LeetCode [336] Palindrome Pairs

336. Palindrome Pairs

Hard

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:

Input: ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]] 
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]

Example 2:

Input: ["bat","tab","cat"]
Output: [[0,1],[1,0]] 
Explanation: The palindromes are ["battab","tabbat"]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

class Solution { bool isPalindrome(string s){ int n = s.size(); int l = 0, r = n-1; while(l<r){ if(s[l++]!=s[r--]) return false; } return true; } public: vector<vector<int>> palindromePairs(vector<string>& words) { set<vector<int>> ret; map<string, int> mp;//word, index; for(int i=0; i<words.size(); ++i){ mp[words[i]] = i; } for(int i=0; i<words.size(); ++i){ string w = words[i]; for(int l=0; l<=w.size(); ++l){ string ls = w.substr(0, l); string rs = w.substr(l); string rls(ls); reverse(rls.begin(), rls.end()); string rrs(rs); reverse(rrs.begin(), rrs.end()); if(mp.count(rls) && mp[rls]!=i && isPalindrome(rs)){ ret.insert(vector<int>{i, mp[rls]}); } if(mp.count(rrs) && mp[rrs]!=i && isPalindrome(ls)){ ret.insert(vector<int>{mp[rrs], i}); } } } return vector<vector<int>>(ret.begin(), ret.end()); } };