【滑动窗口】LeetCode:30串联所有单词的子串

作者推荐

【二叉树】【单调双向队列】LeetCode239:滑动窗口最大值

相关知识点

滑动窗口

题目

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如，如果 words = [“ab”,“cd”,“ef”]， 那么 “abcdef”， “abefcd”，“cdabef”， “cdefab”，“efabcd”， 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
示例 1：
输入：s = “barfoothefoobarman”, words = [“foo”,“bar”]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 “barfoo” 开始位置是 0。它是 words 中以 [“bar”,“foo”] 顺序排列的连接。
子串 “foobar” 开始位置是 9。它是 words 中以 [“foo”,“bar”] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。
示例 2：
输入：s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。
示例 3：
输入：s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 “foobarthe” 开始位置是 6。它是 words 中以 [“foo”,“bar”,“the”] 顺序排列的连接。
子串 “barthefoo” 开始位置是 9。它是 words 中以 [“bar”,“the”,“foo”] 顺序排列的连接。
子串 “thefoobar” 开始位置是 12。它是 words 中以 [“the”,“foo”,“bar”] 顺序排列的连接。
参数范围：
1 <= s.length <= 10⁴
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] 和 s 由小写英文字母组成

滑动窗口

时间复杂度： O(nlen) n是s的长度,len是words[i].length。iWindowWidth = len * words.size();
两层循环：第一层时间复杂度O(len)，第二层:O(n/len)，所以两层循环的时间复杂度是O(n)。

如何判断s[i,i+iWindowWidth) 是 串联子串

将words依次放到一个mHas 中，依次mStrToCount[sSub]–，如果value为0，则移除key。
sSub为s[i,i+len) s[i+len,i+2len) s[i+2len,i+3*len) …
如果mSub为空，说明是串联子串。

s[i,i+iWindowWidth)和s[i+len,i+len+iWindowWidth)

前者多：s[i,i+len)
后者多：s[i+iWindowWidth,i+len+iWindowWidth)
这是滑动窗口的基础。mSub加上前者，减去后者。

代码

核心代码

template<class KEY>
class CKeyCount
{	
public:
	void Add(const KEY& key, int iCount)
	{
		Cnt[key] += iCount;
		if (0 == Cnt[key])
		{
			Cnt.erase(key);
		}
	}
	std::unordered_map<KEY, int> Cnt;
};
class Solution {
public:
	vector<int> findSubstring(string s, vector<string>& words) {
		const int len = words.front().length();
		const int iWindowWidth = len * words.size();
		CKeyCount<string> mStrToCount;
		for (const auto& w : words)
		{
			mStrToCount.Add(w, 1);
		}	
		vector<int> vRet;		
		for (int i = 0; (i < len)&&(i + iWindowWidth <= s.length()); i++)
		{
			int j = i;
			auto mHas = mStrToCount;
			for (; j < i + iWindowWidth; j += len )
			{
				mHas.Add(s.substr(j, len), -1);
			}
			if (mHas.Cnt.empty())
			{
				vRet.emplace_back(j-iWindowWidth);
			}
			for (; j + len <= s.length(); j += len)
			{
				mHas.Add(s.substr(j, len), -1);
				mHas.Add(s.substr(j-iWindowWidth, len), 1);
				if (mHas.Cnt.empty())
				{
					vRet.emplace_back(j - iWindowWidth+len);
				}
			}
		}
		return vRet;
	}
};

测试用例

template<class T>
void Assert(const T& t1, const T& 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()
{
	string s;
	vector<string> words;
	{
		Solution sln;
		s = "barfoothefoobarman", words = { "foo", "bar" };
		auto res = sln.findSubstring(s, words);
		Assert(vector<int>{0, 9}, res);
	}
	{
		Solution sln;
		s = "wordgoodgoodgoodbestword", words = { "word", "good", "best", "word" };
		auto res = sln.findSubstring(s, words);
		Assert(vector<int>{}, res);
	}
	{
		Solution sln;
		s = "barfoofoobarthefoobarman", words = { "bar", "foo", "the" };
		auto res = sln.findSubstring(s, words);
		Assert(vector<int>{6, 9, 12}, res);
	}
}

2023年4月

class Solution {
public:
vector findSubstring(string s, vector& words) {
m_r = words.size();
m_c = words[0].size();
if (s.length() < m_rm_c)
{
return vector();
}
vector vRet;
for (int i = 0; i < m_c; i++ )
{
findSubstring(vRet,i,s.c_str() + i, words);
}
return vRet;
}
void findSubstring(vector& vRet,int iBeginIndex,string s, vector& words) {
std::multiset mLess(words.begin(), words.end()), mMore;
int i = 0;
for (; i + 1 < m_r; i++)
{
DelOrAdd(mLess, mMore, s.substr(m_ci, m_c));
}
for (; i < s.length() / m_c; i++)
{
DelOrAdd(mLess, mMore, s.substr(m_ci, m_c));
int iPreIndex = i - m_r;
if (iPreIndex >= 0)
{
DelOrAdd(mMore, mLess, s.substr(m_ciPreIndex, m_c));
}
if (0 == mLess.size())
{
vRet.emplace_back(iBeginIndex + m_c*(iPreIndex + 1));
}
}
}
void DelOrAdd(std::multiset& mDel, std::multiset& mAdd, const string& s)
{
auto it = mDel.find(s);
if (mDel.end() != it)
{
mDel.erase(it);
return;
}
mAdd.emplace(s);
}
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++ 实现。