本文涉及知识点
字典树 哈希表 字符串
LeetCode 100251. 数组中的最短非公共子字符串
给你一个数组 arr ，数组中有 n 个 非空 字符串。
请你求出一个长度为 n 的字符串 answer ，满足：
answer[i] 是 arr[i] 最短 的子字符串，且它不是 arr 中其他任何字符串的子字符串。如果有多个这样的子字符串存在，answer[i] 应该是它们中字典序最小的一个。如果不存在这样的子字符串，answer[i] 为空字符串。
请你返回数组 answer 。
示例 1：
输入：arr = [“cab”,“ad”,“bad”,“c”]
输出：[“ab”,“”,“ba”,“”]
解释：求解过程如下：
- 对于字符串 “cab” ，最短没有在其他字符串中出现过的子字符串是 “ca” 或者 “ab” ，我们选择字典序更小的子字符串，也就是 “ab” 。
- 对于字符串 “ad” ，不存在没有在其他字符串中出现过的子字符串。
- 对于字符串 “bad” ，最短没有在其他字符串中出现过的子字符串是 “ba” 。
- 对于字符串 “c” ，不存在没有在其他字符串中出现过的子字符串。
示例 2：
输入：arr = [“abc”,“bcd”,“abcd”]
输出：[“”,“”,“abcd”]
解释：求解过程如下：
- 对于字符串 “abc” ，不存在没有在其他字符串中出现过的子字符串。
- 对于字符串 “bcd” ，不存在没有在其他字符串中出现过的子字符串。
- 对于字符串 “abcd” ，最短没有在其他字符串中出现过的子字符串是 “abcd” 。
提示：
n == arr.length
2 public: CTrieNode* AddChar(TData ele, int& iMaxID) { #ifdef _DEBUG if ((ele AddChar(*begin, m_iMaxID); } FreshLeafIndex(pNode); return pNode->m_iLeafIndex; } template CTrieNode* 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 m_root; protected: void FreshLeafIndex(CTrieNode* pNode) { if (-1 == pNode->m_iLeafIndex) { pNode->m_iLeafIndex = m_iLeafCount++; } } int m_iMaxID = 0; int m_iLeafCount = 0; }; class Solution { public: vector shortestSubstrings(vector& arr) { CTrie trie; for (const auto& s : arr) { const int n = s.size(); m_vSubIndex.emplace_back(n + 1, vector(n, -1)); for (int left = 0; left m_iLeafIndex; m_mIndexCount[ptr->m_iLeafIndex].emplace(m_vSubIndex.size()); } } } vector vRet; for (int i = 0; i
测试用例
template void Assert(const T& t1, const T2& t2) { assert(t1 == t2); } template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i旧版代码
template
class CTrieNode
{
public:
CTrieNode* AddChar(TData ele, int& iMaxID)
{
#ifdef _DEBUG
if ((ele = cBegin + iTypeNum))
{
return nullptr;
}
#endif
const int index = ele - cBegin;
auto ptr = m_vPChilds[ele - cBegin];
if (!ptr)
{
m_vPChilds[index] = new CTrieNode();
#ifdef _DEBUG
m_vPChilds[index]->m_iID = ++iMaxID;
m_childForDebug[ele] = m_vPChilds[index];
#endif
}
return m_vPChilds[index];
}
CTrieNode* GetChild(TData ele)const
{
#ifdef _DEBUG
if ((ele = cBegin + iTypeNum))
{
return nullptr;
}
#endif
return m_vPChilds[ele - cBegin];
}
protected:
#ifdef _DEBUG
int m_iID = -1;
std::unordered_map m_childForDebug;
#endif
public:
int m_iLeafIndex = -1;
protected:
CTrieNode* m_vPChilds[iTypeNum] = { nullptr };
};
template
class CTrie
{
public:
int GetLeadCount()
{
return m_iLeafCount;
}
template
int Add(IT begin, IT end)
{
auto pNode = &m_root;
for (; begin != end; ++begin)
{
pNode = pNode->AddChar(begin, m_iMaxID);
}
if (-1 == pNode->m_iLeafIndex)
{
pNode->m_iLeafIndex = m_iLeafCount++;
}
return pNode->m_iLeafIndex;
}
template
CTrieNode 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 m_root;
protected:
int m_iMaxID = 0;
int m_iLeafCount = 0;
};
class Solution {
public:
vector shortestSubstrings(vector& arr) {
CTrie trie;
for (const auto& s : arr)
{
const int n = s.size();
m_vSubIndex.emplace_back(n+1, vector(n, -1));
for (int left = 0; left
{
for (int len = 0; left+len
{
const int index = trie.Add(s.data() + left, s.data() + left + len + 1);
m_vSubIndex.back()[len + 1][left] = index;
m_mIndexCount[index].emplace(m_vSubIndex.size());
}
}
}
vector vRet;
for (int i = 0 ; i
{
vRet.emplace_back(Cal(arr[i], i));
}
return vRet;
}
string Cal(const string& s ,int index)
{
auto& v = m_vSubIndex[index];
const int n = s.size();
for (int len = 1; len 1)
{
sets.erase(std::prev(sets.end()));
}
}
}
if (sets.size())
{
return *sets.begin();
}
}
return “”;
}
vector m_vSubIndex;
unordered_map m_mIndexCount;
int m_r, m_c;
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。
