【字典树 马拉车算法】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 ≠ \neq =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 _DEBUG
		if ((ele < cBegin) || (ele >= cBegin + iTypeNum))
		{
			return nullptr;
		}
#endif
		const int index = ele - cBegin;
		auto ptr = m_dataToChilds[ele - cBegin];
		if (!ptr)
		{
			m_dataToChilds[index] = new CTrieNode();
#ifdef _DEBUG
			m_dataToChilds[index]->m_iID = ++iMaxID;
			m_childForDebug[ele] = m_dataToChilds[index];
#endif
		}
		return m_dataToChilds[index];
	}
	CTrieNode* GetChild(TData ele)
	{
#ifdef _DEBUG
		if ((ele < cBegin) || (ele >= cBegin + iTypeNum))
		{
			return nullptr;
		}
#endif
		return m_dataToChilds[ele - cBegin];
	}
protected:
#ifdef _DEBUG
	int 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++**实现。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/641764.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

huggingface 笔记：PretrainModel

huggingface 笔记：PretrainModel

1 from_pretrained 从预训练模型配置中实例化一个 PyTorch 预训练模型默认情况下&#xff0c;模型使用 model.eval() 设置为评估模式&#xff08;Dropout 模块被禁用&#xff09; 要训练模型&#xff0c;应该首先使用 model.train() 将其设置回训练模式 1.1 主要参数 pretra…
阅读更多...
Python 渗透测试：Redis 数据库 弱密码测试.（6379端口）

Python 渗透测试：Redis 数据库 弱密码测试.（6379端口）

什么是 Redis 数据库 Redis (Remote Dictionary Server) 是一个开源的、内存中的数据结构存储系统&#xff0c;它可以用作数据库、缓存和消息中间件。它支持多种类型的数据结构,如字符串(strings)、哈希(hashes)、列表(lists)、集合(sets)、有序集合(sorted sets)等&#xff0…
阅读更多...
抖音运营_如何做出优质的短视频

抖音运营_如何做出优质的短视频

目录 一 短视频内容的构成 1 图像 2 字幕 3 声音 4 特效 5 描述 6 评论 二 短视频的热门类型 1 颜值圈粉类 2 知识教学类 3 幽默搞笑类 4 商品展示类 5 才艺技能类 6 评论解说类 三 热门短视频的特征 1 产生共鸣 2 正能量 3 紧跟热点话题 4 富有创意 四 短视…
阅读更多...
Android 项目中自定义多个 RadioButton 并排一列选择效果实现

Android 项目中自定义多个 RadioButton 并排一列选择效果实现

文章目录 1、静态版实现1.1、实现要求1.2、实现步骤1.3、代码实现1.4、代码实现说明1.5、结论 2、项目版实现(动态)1、先看效果图2、main的布局文件3、定义RadioButton的属性4、最后在代码中生成我想要的东东5、说明 3、后续优化方向 1、静态版实现 1.1、实现要求 我们需要在…
阅读更多...
Java:图书管理系统

Java:图书管理系统

目录 一.book 1.在book包中的Book 类用来定义和引用书的名字&#xff0c;作者&#xff0c;价格&#xff0c;类型等。 2.在book包中的第二个类是BookList是用来构建书架&#xff0c;和书架上的初始书本&#xff0c; 二、ioperations 1.AddOperation (增加图书) 2.BorrowOp…
阅读更多...
港湾周评|京东图书遭抵制不赢不输

港湾周评|京东图书遭抵制不赢不输

《港湾商业观察》李镭 临近618前夕&#xff0c;数十家出版社抵制京东的消息引发全民关注。一定程上&#xff0c;本就生意冷门或不太赚钱的图书市场&#xff0c;随着这次群起抵制行动&#xff0c;更像是一场行业的反击。 不过&#xff0c;平台有平台的销售策略&#xff0c;毕竟…
阅读更多...
特殊变量笔记2

特殊变量笔记2

案例需求 在demo4.sh中循环打印输出所有输入参数, 体验$*与$的区别 实现步骤 编辑demo4.sh脚本文件 # 增加命令: 实现直接输出所有输入后参数 # 增加命令: 使用循环打印输出所有输入参数演示 编辑demo4.sh文件 直接输出所有输入参数, 与循环方式输出所有输入参数(使用双引…
阅读更多...
工厂生产管理系统

工厂生产管理系统

为应对一些国内验厂&#xff0c;如大疆等&#xff0c;他们需要客户有自己的生产管理系统的&#xff0c;但实际很多公司是没有引入ERP这类的系统的&#xff0c;从而想开发一套简单的生产管理系统。 参考了网上一个比较古老的StorageMange项目&#xff0c;此项目用到DevExpress的…
阅读更多...
体量小但增速快，国内OTA平台与国际巨头差在哪？

体量小但增速快，国内OTA平台与国际巨头差在哪？

5月3日&#xff0c;Booking、Expedia等国际OTA平台相继发布2024年第一季度财报。5月21日&#xff0c;携程发布2024年第一季度财报。至此&#xff0c;国内外主要OTA平台一季度成绩单均已披露。 受益于全球旅游市场复苏&#xff0c;三家OTA平台一季度营收同比均正向增长。增长之…
阅读更多...
码蹄集部分题目（2024OJ赛16期；单调栈集训+差分集训）

码蹄集部分题目（2024OJ赛16期；单调栈集训+差分集训）

&#x1f9c0;&#x1f9c0;&#x1f9c0;单调栈集训 &#x1f96a;单调栈 单调递增栈伪代码&#xff1a; stack<int> st; for(遍历数组) {while(栈不为空&&栈顶元素大于当前元素)//单调递减栈就是把后方判断条件变为小于等于即可{栈顶元素出栈;//同时进行其他…
阅读更多...
Linux系统下Mysql忘记密码怎么解决

Linux系统下Mysql忘记密码怎么解决

一、对Mysql配置文件进行设置 1、找到/etc/mysql/my.cnf路径下&#xff0c;用Vi命令编辑my.cnf配置文件&#xff0c;命令如下&#xff1a; # 以管理员身份登录 sudo su # 输入管理员密码 # 登录成功后&#xff0c;找到Mysql的配置文件-->Mysql配置文件默认在此 cd /etc/my…
阅读更多...
M功能-支付平台(三)

M功能-支付平台(三)

target&#xff1a;离开柬埔寨倒计时-221day 前言 今天周六&#xff0c;但是在柬埔寨还是工作日&#xff0c;想着国内的朋友开始休周末就羡慕呀&#xff0c;记不清在这边过了多少个周六了&#xff0c;多到我已经习惯了。而且今天技术部还停电了&#xff0c;真的是热的受不了呀…
阅读更多...
Autodesk 3ds Max下载，3ds MAX 2024三维建模渲染软件安装包下载安装

Autodesk 3ds Max下载，3ds MAX 2024三维建模渲染软件安装包下载安装

3ds MAX中文版&#xff0c;其强大的功能和灵活的操作为广大用户提供了无限的创意空间&#xff0c;使得高质量动画、最新游戏、设计效果等领域的制作需求得以完美满足。 ​ 作为一款三维建模软件&#xff0c;3ds MAX中文版具备极高的建模精度和渲染质量。它支持多种建模方式&am…
阅读更多...
cocos 通过 electron 打包成 exe 文件，实现通信问题

cocos 通过 electron 打包成 exe 文件，实现通信问题

cocos 通过 electron 打包成 exe 文件&#xff0c;实现通信问题 首先&#xff0c;我使用的 cocos 版本是 2.4.12&#xff0c;遇到一个问题&#xff0c;是啥子呢&#xff0c;就是我要把用 cocos 开发出来的项目打包成一个 exe 可执行程序&#xff0c;使用的是 electron &#xf…
阅读更多...
向传音手机学习产品市场定位与产品需求定义

向传音手机学习产品市场定位与产品需求定义

2024 年第一季度全球智能手机发货量同比增长 11%&#xff0c;排在第一名的是三星&#xff0c;占比 21%&#xff0c;苹果占比 17% 排在第二位&#xff0c;小米 14%排在第三名&#xff0c;传音手机10% 排在第四位&#xff0c;OPPO为 9% 排在第五名。 「非洲之王」传音手机表现十…
阅读更多...
Vulhub——adminer

Vulhub——adminer

文章目录 一、CVE-2021-21311&#xff08;SSRF&#xff09;二、CVE-2021-43008&#xff08;远程文件读取&#xff09; 一、CVE-2021-21311&#xff08;SSRF&#xff09; Adminer是一个PHP编写的开源数据库管理工具&#xff0c;支持MySQL、MariaDB、PostgreSQL、SQLite、MS SQL…
阅读更多...
基本IO接口

基本IO接口

引入 基本输入接口 示例1 示例2&#xff1a;有数据保持能力的外设 #RD端由in指令控制&#xff1a;将数据由端口传输到CPU内存中 #CS244信号由译码电路实现 示例3&#xff1a; a)图中由于输出端口6有连接到端口1&#xff0c;当开关与端点1闭合时期间&#xff0c;仍能维持3端口…
阅读更多...
3D 生成重建013-ProlificDreamer将SDS拓展到VSD算法进行高质量的3D生成

3D 生成重建013-ProlificDreamer将SDS拓展到VSD算法进行高质量的3D生成

3D 生成重建013-ProlificDreamer将SDS拓展到VSD算法进行高质量的3D生成 文章目录 0论文工作1论文方法2效果 0论文工作 **分数蒸馏采样&#xff08;SDS&#xff09;**通过提取预先训练好的大规模文本到图像扩散模型&#xff0c;在文本到3d生成方面显示出了巨大的前景&#xff0…
阅读更多...
软考-程序员 知识点与部分真题梳理

软考-程序员 知识点与部分真题梳理

软考-程序员 知识点与部分真题梳理 参照《程序员教程》第五版划分类别&#xff1b; 持续更新中… 计算机系统基础知识 如何理解和处理浮点数的加减法运算 在计算机科学中&#xff0c;处理浮点数的表示和运算是基础且关键的&#xff0c;尤其是在进行科学计算、图形处理和数据分…
阅读更多...
Autodesk 3DS Max v2025 解锁版安装教程 (3D 建模软件)

Autodesk 3DS Max v2025 解锁版安装教程 (3D 建模软件)

前言 Autodesk 3ds Max 是一款功能强大的 3D 建模和动画解决方案&#xff0c;游戏开发人员、视觉效果艺术家和平面设计师使用它来创建庞大的世界、令人惊叹的场景和引人入胜的虚拟现实 (VR) 体验。 Autodesk 3DS MAX是业界使用最广泛的3D建模和动画软件程序之一&#xff0c;它…
阅读更多...
最新文章

Copyright @ 2022~2023