【map】【滑动窗口】【字典树】C++算法:最长合法子字符串的长度

2023-12-31 17:42:19

作者推荐

动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本

本题涉及知识点

滑动窗口字典树 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>=ij的取值范围为[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 = &trie;
			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++**实现。

文章来源:https://blog.csdn.net/he_zhidan/article/details/135296945
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。