活动网站推广,国外直播,新媒体营销概念,企业建设网站的目的文章目录1. 题目2. 解题2.1 哈希map2.2 Trie树1. 题目
给定一组唯一的单词#xff0c; 找出所有不同 的索引对(i, j)#xff0c;使得列表中的两个单词#xff0c; words[i] words[j] #xff0c;可拼接成回文串。
示例 1:
输入: [abcd,dcba, 找出所有不同 的索引对(i, j)使得列表中的两个单词 words[i] words[j] 可拼接成回文串。
示例 1:
输入: [abcd,dcba,lls,s,sssll]
输出: [[0,1],[1,0],[3,2],[2,4]]
解释: 可拼接成的回文串为 [dcbaabcd,abcddcba,slls,llssssll]示例 2:
输入: [bat,tab,cat]
输出: [[0,1],[1,0]]
解释: 可拼接成的回文串为 [battab,tabbat]来源力扣LeetCode 链接https://leetcode-cn.com/problems/palindrome-pairs 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题 2.1 哈希map
class Solution {
public:vectorvectorint palindromePairs(vectorstring words) {unordered_mapstring, int w_id;setint wdLen;for(int i 0; i words.size(); i){w_id[words[i]] i;//字符串idxwdLen.insert(words[i].size());//字符串长度}vectorvectorint ans;string front, back, revword;for(int i 0; i words.size(); i){revword words[i];//逆序的字符串reverse(revword.begin(),revword.end());if(w_id.count(revword) w_id[revword] ! i)ans.push_back({i, w_id[revword]});//字符串的逆序存在//遍历words[i]可能的子串长度,寻找前部分存在或者后部分存在//且自身剩余的子串为回文int len words[i].size();for(auto it wdLen.begin(); *it len; it){front words[i].substr(0, *it);reverse(front.begin(),front.end());back words[i].substr(*it);if(w_id.count(front) ispalind(back))//前缀的逆存在ans.push_back({i, w_id[front]});}for(auto it wdLen.begin(); *it len; it){front revword.substr(0, *it);back revword.substr(*it);if(w_id.count(front) ispalind(back))//后缀的逆存在ans.push_back({w_id[front], i});}}return ans;}bool ispalind(string s){int l 0, r s.size()-1;while(l r)if(s[l] ! s[r--])return false;return true;}
};904 ms 45.6 MB
2.2 Trie树
class trie
{
public:unordered_mapchar, trie* next;int suffix -1;void insert(string s, int idx){trie *cur this;for(int i s.size()-1; i 0; --i)//单词逆序插入{if(!cur-next[s[i]])cur-next[s[i]] new trie();cur cur-next[s[i]];}cur-suffix idx;//结束时记录单词编号}
};
class Solution {
public:vectorvectorint palindromePairs(vectorstring words) {trie * t new trie(), *cur;vectorvectorint ans;string revword;for(int i 0; i words.size(); i){t-insert(words[i], i);}for(int i 0; i words.size(); i){int n words[i].size(), j, k;cur t;for(j 0; j n; j){if(cur-suffix ! -1 cur-suffix ! i ispalind(words[i], j, n-1))//单词的前缀的逆序在trie中剩余的为回文ans.push_back({i, cur-suffix});if(!cur-next[words[i][j]])break;cur cur-next[words[i][j]];}for(j 0; j n; j)//等号上下只取一次否则答案有重复的{ // j n 时包含了完整字符串的情况cur t;for(k n-j; k n; k)//遍历单词的后缀{if(!cur-next[words[i][k]])break;cur cur-next[words[i][k]];}if(kn cur-suffix ! -1 cur-suffix ! i ispalind(words[i], 0, n-j-1))//该后缀的逆在trie中且前部分为回文ans.push_back({cur-suffix, i});}}return ans;}bool ispalind(string s, int l, int r){while(l r)if(s[l] ! s[r--])return false;return true;}
};940 ms 141.3 MB
trie 改用数组 trie* next[26] {NULL}; 提高运行效率
280 ms 208.5 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
