吉林省现代交通建设有限公司官网站买个人家的网站绑定自己的域名
作者推荐
动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本
本文涉及的基础知识点
C++算法：滑动窗口总结
字典树 map 离线查询
map
map可以分成有序(单调)map和无序(哈希)map。还可分成单键map和多键map（允许重复的键）。本文用：单键无序map。
LeetCode2781:最长合法子字符串的长度
给你一个字符串 word 和一个字符串数组 forbidden 。
如果一个字符串不包含 forbidden 中的任何字符串，我们称这个字符串是 合法 的。
请你返回字符串 word 的一个 最长合法子字符串 的长度。
子字符串 指的是一个字符串中一段连续的字符，它可以为空。
示例 1：
输入：word = “cbaaaabc”, forbidden = [“aaa”,“cb”]
输出：4
解释：总共有 11 个合法子字符串：“c”, “b”, “a”, “ba”, “aa”, “bc”, “baa”, “aab”, “ab”, “abc” 和 “aabc”。最长合法子字符串的长度为 4 。
其他子字符串都要么包含 “aaa” ，要么包含 “cb” 。
示例 2：
输入：word = “leetcode”, forbidden = [“de”,“le”,“e”]
输出：4
解释：总共有 11 个合法子字符串：“l” ，“t” ，“c” ，“o” ，“d” ，“tc” ，“co” ，“od” ，“tco” ，“cod” 和 “tcod” 。最长合法子字符串的长度为 4 。
所有其他子字符串都至少包含 “de” ，“le” 和 “e” 之一。
参数范围：
1 <= word.length <= 105
word 只包含小写英文字母。
1 <= forbidden.length <= 105
1 <= forbidden[i].length <= 10
forbidden[i] 只包含小写英文字母。
滑动窗口+离线查询+map
时间复杂度😮(nmm+nlogn+n)。m = max(forbidden[i].length)为10
第一步：如果s[left,right]等于 forbidden中任何一个字符串，记录在vLeftRight中。本问题等效与：不能包括任意[left,right]的最长子串。
第二步：排序vLeftRight。
第三步：从大到小枚举合法子串的左边界i，计算最大右边界j。
如果s[left,right]等于某个禁止串
| left<i | 无论j为何值，都不会包括对应的禁止串，因为s[left]不在对应的子串中 |
| left>=i | j的取值范围为[i,right)，不能取值right ，否则s[left,right] 就在word[i,j]中。如果多个无法合法的right，取最小值。如果没有合法的right，取m_c。 |
离线查询
由于vLeftRight 已经按left排序，每次处理i之前，先用left >= i的right更新iMin。
代码
核心代码
class Solution {
public:int longestValidSubstring(string word, vector<string>& forbidden) {m_c = word.length();std::unordered_set<string> setHas(forbidden.begin(), forbidden.end());vector<pair<int, int>> vLeftRight;for (int len = 1; len <= 10; len++){for (int left = 0; left + len <= m_c; left++){if (setHas.count(word.substr(left, len))){vLeftRight.emplace_back(left, left + len - 1);}}}sort(vLeftRight.begin(), vLeftRight.end());int iRet = 0;int iMin = m_c;for (int i = m_c - 1; i >= 0; i--){while (vLeftRight.size() && (vLeftRight.back().first >= i)){iMin = min(iMin, vLeftRight.back().second);vLeftRight.pop_back();}iRet = max(iRet, iMin - i);}return iRet;}int m_c;
};
字典树
可以利用字典树，将第一步的时间复杂度降到O(nm)。
template<class TData, TData defData,int iTypeNum = 26, TData cBegin = 'a'>
class CTrie
{
public:CTrie() {m_iID = s_ID++;}int GetLeadCount(){return m_iLeafCount;}template<class IT>int Add(IT begin, IT end){int iLeve = 0;CTrie* pNode = this;for (; begin != end; ++begin){pNode = pNode->AddChar(*begin); pNode->m_iLeve = iLeve++;}if (-1 == pNode->m_iLeafID){pNode->m_iLeafID = ++m_iLeafCount;}return pNode->m_iLeafID;}template<class IT>CTrie* Search(IT begin, IT end){if (begin == end){return this;}if ('.' == *begin){for (auto& ptr : m_vPChilds){if (!ptr){continue;}auto pSearch = ptr->Search(begin + 1, end);if (pSearch){return pSearch;}}return nullptr;}auto ptr = GetChild(*begin);if (nullptr == ptr){return nullptr;}return ptr->Search(begin + 1, end);}CTrie* AddChar(TData ele){if ((ele < cBegin) || (ele >= cBegin + iTypeNum)){return nullptr;}const int index = ele - cBegin;auto ptr = m_vPChilds[index];if (!ptr){m_vPChilds[index] = new CTrie();}return m_vPChilds[index];}CTrie* GetChild(TData ele)const{if ((ele < cBegin) || (ele >= cBegin + iTypeNum)){return nullptr;}return m_vPChilds[ele - cBegin];}
protected:int m_iID;
public:int m_iLeafID=-1;
protected:int m_iLeve=-1;inline static int s_ID = 0;int m_iLeafCount = 0;CTrie* m_vPChilds[iTypeNum] = { nullptr };
};class Solution {
public:int longestValidSubstring(string word, vector<string>& forbidden) {m_c = word.length();CTrie<char,'a'> trie;for (const auto& s : forbidden){trie.Add(s.begin(), s.end());}vector<pair<int, int>> vLeftRight;for (int left = 0; left < m_c ; left++){CTrie<char,'a'>* p = ≜for (int len = 1; left + len <= m_c; len++){p = p->GetChild(word[left + len - 1]);if (nullptr == p){break;}if (p->m_iLeafID > 0){vLeftRight.emplace_back(left, left + len - 1);}}}sort(vLeftRight.begin(), vLeftRight.end());int iRet = 0;int iMin = m_c;for (int i = m_c - 1; i >= 0; i--){while (vLeftRight.size() && (vLeftRight.back().first >= i)){iMin = min(iMin, vLeftRight.back().second);vLeftRight.pop_back();}iRet = max(iRet, iMin - i);}return iRet;}int m_c;
};
2023年7月版
class Solution {
public:
int longestValidSubstring(string word, vector& forbidden) {
m_pHash = std::make_shared< CHashStr<>>(word,26);
std::unordered_set setCode[11];
for (const string& s : forbidden)
{
const int len = s.length();
CHashStr< > hash(s,26);
auto llCode = hash.GetHashExincludeRight(len);
setCode[len].emplace(llCode);
}
std::map<int, int> mEndLen;
for (int i = 0; i < word.size(); i++)
{
for (int len = 1; len <= 10 ; len++)
{
const int end = i + len;
if (end > word.size())
{
continue;
}
int llCode = m_pHash->GetHashExincludeRight(i, end);
if (setCode[len].end() != setCode[len].find(llCode))
{
//目标串不能包括[1,i+len)
mEndLen[i+len] = len;
break;
}
}
}
int begin = 0;
int iMaxLen = 0;
for (const auto& it : mEndLen)
{
const int iCurLen = it.first - begin-1;
iMaxLen = max(iMaxLen, iCurLen);
begin = max(begin,it.first - it.second+ 1);
}
iMaxLen = max(iMaxLen, (int)word.size() - begin);
return iMaxLen;
}
std::shared_ptr< CHashStr<> > m_pHash;
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。
