【字典树 马拉车算法】336. 回文对

本文涉及知识点

字典树 马拉车算法

336. 回文对

给定一个由唯一字符串构成的 0 索引 数组 words 。
回文对 是一对整数 (i, j) ，满足以下条件：
0 <= i, j < words.length，i != j ，并且words[i] + words[j]（两个字符串的连接）是一个回文串
。
返回一个数组，它包含 words 中所有满足 回文对 条件的字符串。
你必须设计一个时间复杂度为 O(sum of words[i].length) 的算法。
示例 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] 由小写英文字母组成。

字典树

n = words.length
字典数tree 各叶子记录符合当前字符串的索引，由于是唯一字符串，所以不可能有相同字符串。
令words2[i]是wrods[i]的逆序。令tree2是words2的字典树。
x1 = words[i].lenght x2=words[j].length
如果 x1 == x2 相等。则words[j]的逆向在字典树存在。注意：i $\ne$j
如果 x1 < x2 。则：令words2[j][x1-1]对应叶子节点wrods[i]，且words2[i][x…]是回文。则[i,j]是回文对。
如果x1 > x2。word[i][x2-1]在tree中对应节点j。words[i][x2…]是回文。
判断回文如果用中心扩展：一个字符串的时间复杂度是O(mm) m = words[i].length
总时间复杂就成了：O(nmm) 超时。
只能用马拉车算法。

内存非常容易超，第一个版本用了两个字典树，空间就超了。换成一个字典树才勉强过。

代码

核心代码

//马拉车计算回文回文
class CPalindrome
{
public:void  CalCenterHalfLen(const string& s){vector<char> v = { '*' };for (const auto& ch : s){v.emplace_back(ch);v.emplace_back('*');}const int len = v.size();vector<int> vHalfLen(len);int center = -1, r = -1;//center是对称中心,r是其右边界（闭）for (int i = 0; i < len; i++){int tmp = 1;if (i <= r){int pre = center - (i - center);tmp = min(vHalfLen[pre], r - i + 1);}for (tmp++; (i + tmp - 1 < len) && (i - tmp + 1 >= 0) && (v[i + tmp - 1] == v[i - tmp + 1]); tmp++);vHalfLen[i] = --tmp;const int iNewR = i + tmp - 1;if (iNewR > r){r = iNewR;center = i;}}m_vOddCenterHalfLen.resize(s.length());m_vEvenCenterHalfLen.resize(s.length());for (int i = 1; i < len; i++){const int center = (i - 1) / 2;const int iHalfLen = vHalfLen[i] / 2;if (i & 1){//原字符串奇数长度m_vOddCenterHalfLen[center] = iHalfLen;}else{m_vEvenCenterHalfLen[center] = iHalfLen;}}}vector<int> m_vOddCenterHalfLen, m_vEvenCenterHalfLen;//vOddHalfLen[i]表示 以s[i]为中心，且长度为奇数的最长回文的半长，包括s[i]//比如："aba" vOddHalfLen[1]为2 "abba" vEvenHalfLen[1]为2
};template<class TData = char, int iTypeNum = 26, TData cBegin = 'a'>
class CTrieNode
{
public:~CTrieNode(){for (auto& [tmp, ptr] : m_dataToChilds) {delete ptr;}}CTrieNode* AddChar(TData ele, int& iMaxID){
#ifdef _DEBUGif ((ele < cBegin) || (ele >= cBegin + iTypeNum)){return nullptr;}
#endifconst int index = ele - cBegin;auto ptr = m_dataToChilds[ele - cBegin];if (!ptr){m_dataToChilds[index] = new CTrieNode();
#ifdef _DEBUGm_dataToChilds[index]->m_iID = ++iMaxID;m_childForDebug[ele] = m_dataToChilds[index];
#endif}return m_dataToChilds[index];}CTrieNode* GetChild(TData ele){
#ifdef _DEBUGif ((ele < cBegin) || (ele >= cBegin + iTypeNum)){return nullptr;}
#endifreturn m_dataToChilds[ele - cBegin];}
protected:
#ifdef _DEBUGint m_iID = -1;std::unordered_map<TData, CTrieNode*> m_childForDebug;
#endif
public:int m_iLeafIndex = -1;
protected://CTrieNode* m_dataToChilds[iTypeNum] = { nullptr };//空间换时间 大约216字节//unordered_map<int, CTrieNode*>    m_dataToChilds;//时间换空间 大约56字节map<int, CTrieNode*>    m_dataToChilds;//时间换空间,空间略优于哈希映射，数量小于256时，时间也优。大约48字节
};
template<class TData = char, int iTypeNum = 26, TData cBegin = 'a'>
class CTrie
{
public:int GetLeadCount(){return m_iLeafCount;}CTrieNode<TData, iTypeNum, cBegin>* AddA(CTrieNode<TData, iTypeNum, cBegin>* par,TData curValue){auto curNode =par->AddChar(curValue, m_iMaxID);FreshLeafIndex(curNode);return curNode;}template<class IT>int Add(IT begin, IT end){auto pNode = &m_root;for (; begin != end; ++begin){pNode = pNode->AddChar(*begin, m_iMaxID);}FreshLeafIndex(pNode);return pNode->m_iLeafIndex;}	template<class IT>CTrieNode<TData, iTypeNum, cBegin>* Search(IT begin, IT end){auto ptr = &m_root;for (; begin != end; ++begin){ptr = ptr->GetChild(*begin);if (nullptr == ptr){return nullptr;}}return ptr;}CTrieNode<TData, iTypeNum, cBegin> m_root;
protected:void FreshLeafIndex(CTrieNode<TData, iTypeNum, cBegin>* pNode){if (-1 == pNode->m_iLeafIndex){pNode->m_iLeafIndex = m_iLeafCount++;}}int m_iMaxID = 0;int m_iLeafCount = 0;
};class Solution {
public:vector<vector<int>> palindromePairs(vector<string>& words) {{CTrie<> tree;for (const auto& s : words) {				tree.Add(s.rbegin(), s.rend());}for (int i = 0; i < words.size(); i++) {const auto& s = words[i];auto ptr = tree.Search(s.begin(), s.end());if ((nullptr != ptr) && (-1 != ptr->m_iLeafIndex) && (i != ptr->m_iLeafIndex)) {m_vRet.emplace_back(vector<int>{ i, ptr->m_iLeafIndex });}}for (int i = 0; i < words.size(); i++) {const auto& s = words[i];CPalindrome p1;p1.CalCenterHalfLen(s);Do(s,i, &tree.m_root, p1, false);}}{CTrie<> tree;for (const auto& s : words) {tree.Add(s.begin(), s.end());}for (int i = 0; i < words.size(); i++) {string s (words[i].rbegin(), words[i].rend());CPalindrome p1;p1.CalCenterHalfLen(s);Do(s, i, &tree.m_root, p1, true);}}		return m_vRet;}void Do  (const std::string& s, int i ,CTrieNode<char, 26, (char)97>* ptr1, CPalindrome& p1, bool bRev){for (int j = 0; j < s.length(); j++) {if (nullptr == ptr1) { break; }if (-1 != ptr1->m_iLeafIndex) {const int len = s.length() - j;const int needHalfLen = (len + 1) / 2;bool bOdd = 1 & (len);auto center = (j + s.length() - 1) / 2;const auto& iHalfLen = bOdd ? p1.m_vOddCenterHalfLen[center] : p1.m_vEvenCenterHalfLen[center];if (iHalfLen >= needHalfLen) {if (bRev) {m_vRet.emplace_back(vector<int>{ ptr1->m_iLeafIndex, i});}else {m_vRet.emplace_back(vector<int>{i, ptr1->m_iLeafIndex});}}}ptr1 = ptr1->GetChild(s[j]);}};vector<vector<int>> m_vRet;
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}}int main()
{vector<string> words;{Solution sln;words = { "bat","tab","cat" };auto res = sln.palindromePairs(words);Assert(res, { {0,1},{1,0} });}{Solution sln;words = { "a","" };auto res = sln.palindromePairs(words);Assert(res, { {0,1},{1,0} });}{Solution sln;words = { "abcd","dcba","lls","s","sssll" };auto res = sln.palindromePairs(words);Assert(res, { {0,1},{1,0},{3,2},{2,4} });}}

2023年哈希

class Solution {
public:vector<vector<int>> palindromePairs(vector<string>& words) {vector<int> indexs;for (int i = 0; i < words.size(); i++){indexs.emplace_back(i);}std::sort(indexs.begin(), indexs.end(), [&](const int& i1,const int& i2){return words[i1].length() < words[i2].length();});vector<vector<int>> vRet;std::unordered_map<string, int> mStrIndexs;int iEmptyStrindex = -1;for (int ii = 0; ii < words.size(); ii++){const int i = indexs[ii];const string& word = words[i];string strRev(word.rbegin(), word.rend());const int iUpper = word.length() - 1;const char* pRev = strRev.c_str() +  1;{//左边是回文vector<char> vRevRight(word.rbegin(), word.rend());C2DynaHashStr<> hs(26), hsRev(26);for (int j = 0; j < word.size(); j++){hs.push_back(word[j]);hsRev.push_front(word[j]);if (hs == hsRev){vRevRight[iUpper - j] = '\0';if (mStrIndexs.count(vRevRight.data())){vRet.emplace_back(vector<int>{ mStrIndexs[vRevRight.data()], i});}}}}{C2DynaHashStr<> hs(26), hsRev(26);for (int j = word.size() - 1; j >= 0; j--){hs.push_back(word[j]);hsRev.push_front(word[j]);if (hs == hsRev){if (mStrIndexs.count(pRev)){vRet.emplace_back(vector<int>{i, mStrIndexs[pRev]});}}pRev++;}}{if (mStrIndexs.count(strRev)){vRet.emplace_back(vector<int>{i, mStrIndexs[strRev]});vRet.emplace_back(vector<int>{ mStrIndexs[strRev], i});}}mStrIndexs[word] = i;}sort(vRet.begin(), vRet.end());return vRet;}bool Check(const string& str,C2HashStr<>& hs, C2HashStr<>& hsRev, int left, int r){/*while (l < r){if (str[l] != str[r]){return false;}l++;r--;}*/const int iUpper = str.length() - 1;return hs.GetHash(left, r) == hsRev.GetHash(iUpper - r, iUpper - left);}
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。