[前缀树]leetcode336：回文对(hard)

回文对(hard)"/>

[前缀树]leetcode336：回文对(hard)

题目：

题解：

第一步：将<单词，下标>存放在hashmap中（使用hashmap代替前缀树），将单词的长度存放在set中。

---

第二步：遍历单词数组，将遍历的到的单词先进行反转：

• 1）第一种情况：单词数组中存在两个长度相等且互为回文的单词。比如：abcd和dcba，当我们遍历到abcd时，将其反转为dcba，然后我们判断dcba是否在map中，并且dcba的下标要和abcd的下标不一致。（因为类似bb这种单个字符重复的字符串，在反转之后得到的字符串的下标任然是它自己。）
• 2）第二种情况：单词数组中两个长度不一的单词构造回文对。比如abcdd、dbc或aabcd、bcd，先说abcdd、dbc，abcdd反转后得到的字符串为ddabc，那我们就需要在set表中找到长度为3的单词，然后截掉长度为3的子字符串后判断剩下的dd是否回文，并且还需要判断长度为3的字符串abc是否在map表中。然后我们再说说aabcd、bcd，aabcd反转后得到的字符串为bcdaa，那我们也需要在set表中找到长度为3的单词，截掉长度为3的子字符串后判断剩下的aa是否回文，并且还需要判断长度为3的字符串bcd是否在map表中。

代码如下：

class Solution {
public:vector<vector<int>> palindromePairs(vector<string>& words) {if(words.empty())return {};vector<vector<int>> result;unordered_map<string,int> m;//单词->下标set<int> s;//单词的长度排序//第一次遍历：建立map表和set表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 word=words[i];int size=word.size();reverse(word.begin(),word.end());//反转单词//第一种情况：回文对就是两个长度相等的单词互为反转字符串,比如abcd与dcba,但是要排除bb这种反转后依旧是自己的字符串if(m.count(word)!=0&&m[word]!=i){result.push_back({i,m[word]});}//第二种情况：回文对是两个长度不一的单词，比如lls,反转后为sll,我们在set中找到长度为1的单词，减去长度1的后ll是否为回文对auto a=s.find(size);for(auto it=s.begin();it!=a;++it){int d=*it;//set中长度为d的单词//处理str=回文对+字母，比如ddcba,我们找到长度为3的单词，就判断dd是否回文，然后判断减去dd后的cba是否在map中if(isValid(word,0,size-d-1)&&m.count(word.substr(size-d)))result.push_back({i,m[word.substr(size-d)]});//处理str=字母+回文对，比如bcdaa,我们找到长度为3的单词，就判断aa是否回文，然后就判断减去aa后的bcd是否在map中if(isValid(word,d,size-1)&&m.count(word.substr(0,d)))result.push_back({m[word.substr(0,d)],i});}} return result;}bool isValid(string word,int left,int right)//判断word是否为回文对{while(left<right){if(word[left++]!=word[right--])return false;}return true;}
};