Description
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"]
分析
- 要用到哈希表来建立每个单词和其位置的映射,然后需要一个set来保存出现过的单词的长度,算法的思想是,遍历单词集,对于遍历到的单词,对其翻转一下,然后在哈希表查找翻转后的字符串是否存在,注意不能和原字符串的坐标位置相同,因为有可能一个单词翻转后和原单词相等。
- 现在只是处理了bat和tab的情况,还存在abcd和cba,dcb和abcd这些情况需要考虑,这就需要用set,由于set是自动排序的,可以找到当前单词长度在set中的iterator,然后从开头开始遍历set,遍历比当前单词小的长度,比如abcdd翻转后为ddcba,发现set中有长度为3的单词,然后判断dd是否为回文串,若是,再看cba是否存在于哈希表,若存在,则说明abcdd和cba是回文对,存入结果中;
- 对于dcb和aabcd这类的情况也是同样处理,我们要在set里找的字符串要在遍历到的字符串的左边和右边分别尝试,看是否是回文对,这样遍历完单词集,就能得到所有的回文对。
代码
class Solution {
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
vector<vector<int>> res;
unordered_map<string,int> m;
set<int> s;
for(int i=0;i<words.size();i++){
m[words[i]]=i;
s.insert(words[i].size());
}
for(int i=0;i<words.size();i++){
string t=words[i];
int len=words[i].size();
reverse(t.begin(),t.end());
if(m.count(t)&&m[t]!=i){
res.push_back({i,m[t]});
}
auto a=s.find(len);
for(auto it=s.begin();it!=a;it++){
int d=*it;
if(isValid(t,0,len-d-1)&&m.count(t.substr(len-d))){
res.push_back({i,m[t.substr(len-d)]});
}
if(isValid(t,d,len-1)&&m.count(t.substr(0,d))){
res.push_back({m[t.substr(0,d)],i});
}
}
}
return res;
}
bool isValid(string t,int left,int right){
while(left<right){
if(t[left++]!=t[right--]) return false;
}
return true;
}
};