Given a list of unique words, return all the pairs of the distinct indices (i, j) in the given list, so that the concatenation of the two words words[i] + words[j] is a palindrome.
Example 1:
Input: words = ["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: words = ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]
Example 3:
Input: words = ["a",""]
Output: [[0,1],[1,0]]
Solution:
Approach:
Find the possible palindromic substring
Find the reverse of left part to make it palindrome
class Solution
{
public:
bool isPalin(string s)
{
int i = 0;
int j = s.length() - 1;
while (i <= j)
{
if (s[i] != s[j])
{
return false;
}
i++;
j--;
}
return true;
}
vector<vector<int>> palindromePairs(vector<string> &words)
{
unordered_map<string, int> m;
vector<vector<int>> res;
for (int i = 0; i < words.size(); i++)
{
m[words[i]] = i;
}
if (m.find("") != m.end())
{
int idx = m[""];
for (int i = 0; i < words.size(); i++)
{
if (words[i] == "")
{
continue;
}
string s = words[i];
reverse(s.begin(), s.end());
if (s == words[i])
{
res.push_back({i, idx});
res.push_back({idx, i});
}
}
}
for (int i = 0; i < words.size(); i++)
{
int n = words[i].length();
for (int k = 1; k <= n; k++)
{
string ls = words[i].substr(0, k);
string rs = words[i].substr(k, n - k);
string rrev = rs;
reverse(rrev.begin(), rrev.end());
string lrev = ls;
reverse(lrev.begin(), lrev.end());
if (isPalin(ls) && m.find(rrev) != m.end() && rs != "" && m[rrev] != i)
{
res.push_back({m[rrev], i});
}
if (isPalin(rs) && m.find(lrev) != m.end() && m[lrev] != i)
{
res.push_back({i, m[lrev]});
}
}
}
return res;
}
};