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"]
Links: https://leetcode.com/discuss/93599/easy-to-understand-ac-c-solution-o-n-k-2-using-map
Solution 1:
class Solution {
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
unordered_map<string, int> dict;
vector<vector<int>> ans;
// build dictionary
for(int i = ; i < words.size(); i++) {
string key = words[i];
reverse(key.begin(), key.end());
dict[key] = i;
}
// edge case: if empty string "" exists, find all palindromes to become pairs ("", self)
if(dict.find("")!=dict.end()){
for(int i = ; i < words.size(); i++){
if(i == dict[""]) continue;
if(isPalindrome(words[i])) ans.push_back({dict[""], i});
}
}
for(int i = ; i < words.size(); i++) {
for(int j = ; j < words[i].size(); j++) {
string left = words[i].substr(, j);
string right = words[i].substr(j, words[i].size() - j);
if(dict.find(left) != dict.end() && isPalindrome(right)
&& dict[left] != i) {
ans.push_back({i, dict[left]});
}
if(dict.find(right) != dict.end() && isPalindrome(left)
&& dict[right] != i) {
ans.push_back({dict[right], i});
}
}
}
return ans;
}
bool isPalindrome(string str){
int i = ;
int j = str.size() - ;
while(i < j) {
if(str[i++] != str[j--]) return false;
}
return true;
}
};Solution 2: