大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
给定一组 互不相同 的单词, 找出所有 不同 的索引对 (i, j),使得列表中的两个单词, words[i] + words[j] ,可拼接成回文串。
创新互联公司一直秉承“诚信做人,踏实做事”的原则,不欺瞒客户,是我们最起码的底线! 以服务为基础,以质量求生存,以技术求发展,成交一个客户多一个朋友!为您提供网站制作、成都网站制作、成都网页设计、成都微信小程序、成都网站开发、成都网站制作、成都软件开发、重庆APP软件开发是成都本地专业的网站建设和网站设计公司,等你一起来见证!示例 1:
输入:words = [“abcd”,“dcba”,“lls”,“s”,“sssll”]
输出:[[0,1],[1,0],[3,2],[2,4]]
解释:可拼接成的回文串为 [“dcbaabcd”,“abcddcba”,“slls”,“llssssll”]
示例 2:
输入:words = [“bat”,“tab”,“cat”]
输出:[[0,1],[1,0]]
解释:可拼接成的回文串为 [“battab”,“tabbat”]
示例 3:
输入:words = [“a”,“”]
输出:[[0,1],[1,0]]
提示:
1<= words.length<= 5000
0<= words[i].length<= 300
words[i] 由小写英文字母组成
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/palindrome-pairs
方法一:字典树
C++提交内容:
// 双指针判断是否是回文: 这里直接用字符串加范围,减少字符串临时创建
bool IsPalindrome(const string& s, int i, int j)
{while (i< j)
{if (s[i] != s[j])
{return false;
}
++i;
--j;
}
return true;
}
// 字典树的结点,目前就是26个字母来构建
struct Node
{Node* children[26];
// 当前节点的包含完整单词的序号
vectorwords;
// 当前节点之后部分字符串能构成回文串的序号
vectorsuffixs;
Node()
{memset(children, 0, sizeof(children));
}
};
class Solution {public:
vector>palindromePairs(vector& words) {Node* root = new Node();
int n = words.size();
// 基于逆序构建字典树
for (int i = 0; i< n; ++i)
{// 反序番茨
string revWord = words[i];
reverse(revWord.begin(), revWord.end());
Node* curr = root;
int nj = revWord.size();
// 当前单词就可以构成回文串,则插入到suffix里面
if (IsPalindrome(revWord, 0, nj-1))
{curr->suffixs.push_back(i);
}
for (int j = 0; j< nj; ++j)
{int c = revWord[j] - 'a';
if (curr->children[c] == nullptr)
{curr->children[c] = new Node();
}
curr = curr->children[c];
// 判断后续 j+1~n部分是否可以构成回文串
if (IsPalindrome(revWord, j+1, nj-1))
{curr->suffixs.push_back(i);
}
}
// 表示这个节点对应于单词i的结束
curr->words.push_back(i);
}
vector>res;
// 再次正序遍历来获取回文串对
for (int i = 0; i< n; ++i)
{Node* curr = root;
int j = 0;
int nj = words[i].size();
for (; j< nj; ++j)
{// 判断后续是否已经是回文 ,那么就可以和当前节点 words 构成回文串,等同于模式 A1+A2+B
if (IsPalindrome(words[i], j, nj-1))
{// 记得排除自己的序号
for (int k : curr->words)
{if (k != i)
{res.push_back({i, k});
}
}
}
// 找下一个结点,如果找不到则失败,直接break
int c = words[i][j] - 'a';
if (curr->children[c] == nullptr)
{break;
}
curr = curr->children[c];
}
// 这里只考虑完全遍历完的情况,去找模式 A+B1+B2的情况来构建回文串
if (j == nj)
{for (int k : curr->suffixs)
{if (k != i)
{res.push_back({i,k});
}
}
}
}
return res;
}
};
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧