【字典树】【字符串】【前缀】100268. 最长公共后缀查询

作者推荐

视频算法专题

本文涉及知识点

字典树字符串前缀

LeetCode 100268. 最长公共后缀查询

给你两个字符串数组 wordsContainer 和 wordsQuery 。
对于每个 wordsQuery[i] ，你需要从 wordsContainer 中找到一个与 wordsQuery[i] 有最长公共后缀的字符串。如果 wordsContainer 中有两个或者更多字符串有最长公共后缀，那么答案为长度最短的。如果有超过两个字符串有相同最短长度，那么答案为它们在 wordsContainer 中出现更早的一个。
请你返回一个整数数组 ans ，其中 ans[i]是 wordsContainer中与 wordsQuery[i] 有最长公共后缀字符串的下标。
示例 1：
输入：wordsContainer = [“abcd”,“bcd”,“xbcd”], wordsQuery = [“cd”,“bcd”,“xyz”]
输出：[1,1,1]
解释：
我们分别来看每一个 wordsQuery[i] ：
对于 wordsQuery[0] = “cd” ，wordsContainer 中有最长公共后缀 “cd” 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。
对于 wordsQuery[1] = “bcd” ，wordsContainer 中有最长公共后缀 “bcd” 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。
对于 wordsQuery[2] = “xyz” ，wordsContainer 中没有字符串跟它有公共后缀，所以最长公共后缀为 “” ，下标为 0 ，1 和 2 的字符串都得到这一公共后缀。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。
示例 2：
输入：wordsContainer = [“abcdefgh”,“poiuygh”,“ghghgh”], wordsQuery = [“gh”,“acbfgh”,“acbfegh”]
输出：[2,0,2]
解释：
我们分别来看每一个 wordsQuery[i] ：
对于 wordsQuery[0] = “gh” ，wordsContainer 中有最长公共后缀 “gh” 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 2 的字符串，因为它的长度为 6 ，是最短的字符串。
对于 wordsQuery[1] = “acbfgh” ，只有下标为 0 的字符串有最长公共后缀 “fgh” 。所以尽管下标为 2 的字符串是最短的字符串，但答案是 0 。
对于 wordsQuery[2] = “acbfegh” ，wordsContainer 中有最长公共后缀 “gh” 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 2 的字符串，因为它的长度为 6 ，是最短的字符串。

提示：
1 <= wordsContainer.length, wordsQuery.length <= 10⁴
1 <= wordsContainer[i].length <= 5 * 10³
1 <= wordsQuery[i].length <= 5 * 10³
wordsContainer[i] 只包含小写英文字母。
wordsQuery[i] 只包含小写英文字母。
wordsContainer[i].length 的和至多为 5 * 10⁵ 。
wordsQuery[i].length 的和至多为 5 * 10⁵ 。

字典树

将字符串全部反序，则后缀变成前缀。用字典树实现。
每个节点，包括根节点都要记录经过此节点的字符串的长度和下标。
内存超了的原因：
字典树的字符数最多是 5*10⁵ 每个字符 26种。合计：1.3e7，接近内存超出的边缘。
将向量改成哈希映射后，还是不行。
开始用set<pair<int,int>> 记录最小值，换成pair就可以了。

代码

template<class TData = char, int iTypeNum = 26, TData cBegin = 'a'>
class CTrieNodeEx
{
public:
	CTrieNodeEx* AddChar(TData ele)
	{
		const int index = ele - cBegin;
		if (!m_vPChilds.count(index))		
		{
			m_vPChilds[index] = new CTrieNodeEx();
		}
		return m_vPChilds[index];
	}
	CTrieNodeEx* GetChild(TData ele)
	{
		const int index = ele - cBegin;
		if (m_vPChilds.count(index))
		{
			return m_vPChilds[index];
		}
		return nullptr;
	}
public:
	pair<int, int> m_lenIndex = { 1000'1000,0 };
protected:
	unordered_map<int, CTrieNodeEx*> m_vPChilds;
};


template<class TData = char, int iTypeNum = 26, TData cBegin = 'a'>
class CTrieEx
{
public:	
	void Add(const string& str,int index)
	{
		auto lenIndex = std::make_pair((int)str.length(),index);
		auto pNode = &m_root;
		if (lenIndex < pNode->m_lenIndex)
		{
			pNode->m_lenIndex = lenIndex;
		}
		for (const auto& ch : str )
		{
			pNode = pNode->AddChar(ch);
			if (lenIndex < pNode->m_lenIndex)
			{
				pNode->m_lenIndex = lenIndex;
			}
		}
	}
	int Find(const string& str)
	{
		auto pNode = &m_root;
		for (const auto& ch : str)
		{
			auto tmp = pNode->GetChild(ch);
			if (nullptr == tmp)
			{
				break;
			}
			pNode = tmp;
		}
		return pNode->m_lenIndex.second;
	}
	CTrieNodeEx<TData, iTypeNum, cBegin> m_root;	
};

class Solution {
public:
	vector<int> stringIndices(vector<string>& wordsContainer, vector<string>& wordsQuery) {
		CTrieEx trie;
		for (int i = 0; i < wordsContainer.size(); i++)
		{
			string strRev(wordsContainer[i].rbegin(), wordsContainer[i].rend());
			trie.Add(strRev, i);
		}
		vector<int> vRet;
		for (int i = 0; i < wordsQuery.size(); i++)
		{
			string strRev(wordsQuery[i].rbegin(), wordsQuery[i].rend());
			vRet.emplace_back(trie.Find(strRev));
		}
		return vRet;
	}
};

测试用例

template<class T, class T2>
void Assert(const T& t1, const T2& 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> wordsContainer, wordsQuery;
	{
		Solution sln;
		wordsContainer = { "abcd", "bcd", "xbcd" }, wordsQuery = { "cd", "bcd", "xyz" };
		auto res = sln.stringIndices(wordsContainer, wordsQuery);
		Assert({ 1,1,1 }, res);
	}
	{
		Solution sln;
		wordsContainer = { "abcdefgh", "poiuygh", "ghghgh" }, wordsQuery = { "gh", "acbfgh", "acbfegh" };
		auto res = sln.stringIndices(wordsContainer, wordsQuery);
		Assert({ 2,0,2 }, res);
	}
}

扩展阅读

视频课程

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

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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛