# Leetcode 336 Solution

https://leetcode.com/problems/palindrome-pairs

## Solution

``````class Solution {
public:
bool ispar(const string& str, int l, int r)
{
while (l < r)
{
if (str[l] != str[r])
break;

l++;
r--;
}

return l >= r;
}

vector<vector<int>> palindromePairs(vector<string>& words) {
map<string, int> pos;
vector<vector<int>> res;

for (int i = 0; i < words.size(); i++)
pos[words[i]] = i;

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

if (pos.find(rword) != pos.end() && pos[rword] != i)
{
vector<int> pair;
pair.push_back(pos[rword]);
pair.push_back(i);
res.push_back(pair);
}

for (int j = 0; j < word.size(); j++)
{
if (ispar(rword, rword.size() - 1 - j, rword.size() - 1) && pos.find(rword.substr(0, rword.size() - 1 - j)) != pos.end())
{
vector<int> pair;
pair.push_back(pos[rword.substr(0, rword.size() - 1 - j)]);
pair.push_back(i);
res.push_back(pair);
}

if (ispar(rword, 0, j) && pos.find(rword.substr(j + 1)) != pos.end())
{
vector<int> pair;
pair.push_back(i);
pair.push_back(pos[rword.substr(j + 1)]);
res.push_back(pair);
}
}
}

return res;
}
};
``````