题目
给定一个字符串 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 <= 104
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++ 实现。
