作者推荐

动态规划 多源路径 字典树 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 <= 10⁵
word 只包含小写英文字母。
1 <= forbidden.length <= 10⁵
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]等于某个禁止串

离线查询

由于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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

字典树

可以利用字典树，将第一步的时间复杂度降到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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

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 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++**实现。