## Palindrome Pairs

• Time:O(nk^2), where n = |\texttt{words}| and k = |\texttt{words[i]}
• Space:O(nk)

## C++

``````class Solution {
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
vector<vector<int>> ans;
unordered_map<string, int> map;  // {reversed word: its index}

for (int i = 0; i < words.size(); ++i) {
string word = words[i];
reverse(begin(word), end(word));
map[word] = i;
}

for (int i = 0; i < words.size(); ++i) {
const string& word = words[i];
// special case to prevent duplicate calculation
if (map.count("") && map[""] != i && isPalindrome(word))
ans.push_back({i, map[""]});
for (int j = 1; j <= word.length(); ++j) {
const string& l = word.substr(0, j);
const string& r = word.substr(j);
if (map.count(l) && map[l] != i && isPalindrome(r))
ans.push_back({i, map[l]});
if (map.count(r) && map[r] != i && isPalindrome(l))
ans.push_back({map[r], i});
}
}

return ans;
}

private:
bool isPalindrome(const string& word) {
int l = 0;
int r = word.length() - 1;
while (l < r)
if (word[l++] != word[r--])
return false;
return true;
}
};
``````

## JAVA

``````class Solution {
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> ans = new ArrayList<>();
Map<String, Integer> map = new HashMap<>(); // {reversed word: its index}

for (int i = 0; i < words.length; ++i)
map.put(new StringBuilder(words[i]).reverse().toString(), i);

for (int i = 0; i < words.length; ++i) {
final String word = words[i];
// special case to prevent duplicate calculation
if (map.containsKey("") && map.get("") != i && isPalindrome(word))
for (int j = 1; j <= word.length(); ++j) {
final String l = word.substring(0, j);
final String r = word.substring(j);
if (map.containsKey(l) && map.get(l) != i && isPalindrome(r))
if (map.containsKey(r) && map.get(r) != i && isPalindrome(l))
}
}

return ans;
}

private boolean isPalindrome(final String word) {
int l = 0;
int r = word.length() - 1;
while (l < r)
if (word.charAt(l++) != word.charAt(r--))
return false;
return true;
}
}
``````

## Python

``````class Solution:
def palindromePairs(self, words: List[str]) -> List[List[int]]:
ans = []
dict = {word[::-1]: i for i, word in enumerate(words)}

for i, word in enumerate(words):
if "" in dict and dict[""] != i and word == word[::-1]:
ans.append([i, dict[""]])

for j in range(1, len(word) + 1):
l = word[:j]
r = word[j:]
if l in dict and dict[l] != i and r == r[::-1]:
ans.append([i, dict[l]])
if r in dict and dict[r] != i and l == l[::-1]:
ans.append([dict[r], i])

return ans
``````