本文目录
题目描述
给定一个字符串 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"] 顺序排列的连接
个人C++解答
GYL
内存爆炸：
考虑采用两个哈希表，滑动窗口一个，原words一个，每个窗口建立一个表，判断是否与原表相同，相同的话该子串有效，否则无效；
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
std::unordered_map<string, int> myMap;
for (auto word : words) myMap[word] += 1;
vector<int> result;
int word_length = words[0].size();
int word_num = words.size();
if (s.size() < word_length * words.size())
return result;
int left = 0, right = word_length * word_num;
std::unordered_map<string, int> myTemp;
for (; right <= s.size(); left++, right++) {
myTemp.clear();
for (int t_l = 0; t_l < word_num; t_l++) {
string temp_key = s.substr(left, right).substr(word_length * t_l, word_length);
myTemp[temp_key] += 1;
}
if(areMapsEqual(myTemp,myMap)) result.push_back(left);
}
return result;
}
bool areMapsEqual(const std::unordered_map<string, int>& map1,
const std::unordered_map<string, int>& map2) {
if (map1.size() != map2.size()) {
return false;
}
for (const auto& pair : map1) {
auto it = map2.find(pair.first);
if (it == map2.end() || it->second != pair.second) {
return false;
}
}
return true;
}
};
GYL
内存爆炸:
依次滑动单个窗口，拆分字符串，传入HashMap，遍历words，每个HashMap[word]-=1，判断HashMap的大小是否为0，为0的话说明拆分成的子串每个都在words中存在过且数量对应；
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
unordered_map<string, int> myMap;
vector<int> result;
int word_length = words[0].size();
int word_num = words.size();
if (s.size() < word_length * words.size())
return result;
int left = 0, right = word_length * word_num,flag = 0;
for (; right <= s.size(); left++, right++) {
flag = 0;
myMap.clear();
for (int t_l = 0; t_l < word_num; t_l++) {
string temp_key = s.substr(left, right).substr(word_length * t_l, word_length);
myMap[temp_key] ++;
}
for(auto word:words){
myMap[word]--;
if(myMap[word]==0){
myMap.erase(word);
}
}
if(myMap.size()==0)
result.push_back(left);
}
return result;
}
};
GYL
内存允许，时间爆炸：
优化代码，使得裁剪字符串和构建哈希表的次数变少，从而减少内存开销，时间复杂度没变
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> result;
if (s.empty() || words.empty()) return result;
if (s.size() < words[0].size() * words.size()) return result;
int wordLen = words[0].size();
int wordNum = words.size();
unordered_map<string, int> wordCount;
for (const string& word : words) {
wordCount[word]++;
}
int totalLen = wordLen * wordNum;
for (int left = 0; left <= s.size() - totalLen; left++) {
unordered_map<string, int> matched(wordCount);
for (int right = left; right < left + totalLen; right += wordLen) {
string word = s.substr(right, wordLen);
if (matched.find(word) == matched.end()) break;
matched[word]--;
if (matched[word] == 0) {
matched.erase(word);
}
}
if (matched.empty()) {
result.push_back(left);
}
}
return result;
}
};
GPT优化代码
核心优化：for (int i = 0; i < wordLen; i++) { unordered_map<string, int> window; int left = i, right = i, count = 0;从每个可能的起点（0 到 wordLen - 1）开始，确保所有可能的起点都能被覆盖。
GPT
时间复杂度降低到了 O(n * wordLen), 其中 n 是字符串 s 的长度，wordLen 是单词的长度
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> result;
if (s.empty() || words.empty()) return result;
int wordLen = words[0].size();
int wordNum = words.size();
int totalLen = wordLen * wordNum;
if (s.size() < totalLen) return result;
unordered_map<string, int> wordCount;
for (const string& word : words) {
wordCount[word]++;
}
// Iterate over each possible starting index within the first word length
for (int i = 0; i < wordLen; i++) {
unordered_map<string, int> window;
int left = i, right = i, count = 0;
while (right + wordLen <= s.size()) {
string word = s.substr(right, wordLen);
right += wordLen;
if (wordCount.find(word) != wordCount.end()) {
window[word]++;
count++;
// If the word count exceeds, slide the window from the left
while (window[word] > wordCount[word]) {
string leftWord = s.substr(left, wordLen);
window[leftWord]--;
left += wordLen;
count--;
}
// If count equals wordNum, a valid substring is found
if (count == wordNum) {
result.push_back(left);
}
} else {
// Reset the window
window.clear();
count = 0;
left = right;
}
}
}
return result;
}
};
