回文对(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;}
};
更多推荐
[前缀树]leetcode336:回文对(hard)
发布评论