30. 串联所有单词的子串 c++自己解答无法通过,可以帮我看看代码错在哪里吗？

Question

给定一个字符串 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 由小写英文字母组成

我想知道为什么我的代码无法通过测试例，错误在哪，麻烦大神看看
我的回答

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        int m = words.size(), n = words[0].size(), ls = s.size();
        unordered_map<string, int> win, wordsMap;
        for (int i = 0; i < m; i++) {
            wordsMap[words[i]]++;
        }
        for (int k = 0; k < m; k += n) {
            win[s.substr(k, m)]++;
        }
        if (wordsMap == win) {
            res.push_back(0);
        }
        for (int j = 0; j < n && j <= ls - m * n; j++) {
            for (int start = j; start <= ls - m * n; start += n) {
                win.erase(s.substr(start, n));
                win.erase(s.substr(start + m * n, n));
            }
            if (wordsMap == win) {
            res.push_back(j + 1);
            }
        }

        return res;
    }
};

官方题解与代码：

方法一：滑动窗口
思路

此题是「438. 找到字符串中所有字母异位词」的进阶版。不同的是第 438 题的元素是字母，而此题的元素是单词。可以用类似「438. 找到字符串中所有字母异位词的官方题解」的方法二的滑动窗口来解这题。

记 words 的长度为 m，words 中每个单词的长度为 n，s 的长度为 ls。首先需要将 s 划分为单词组，每个单词的大小均为 n （首尾除外）。这样的划分方法有 n 种，即先删去前 i （i=0∼n−1）个字母后，将剩下的字母进行划分，如果末尾有不到 n 个字母也删去。对这 n 种划分得到的单词数组分别使用滑动窗口对 words 进行类似于「字母异位词」的搜寻。

划分成单词组后，一个窗口包含 s 中前 m 个单词，用一个哈希表 differ 表示窗口中单词频次和 words 中单词频次之差。初始化 differ 时，出现在窗口中的单词，每出现一次，相应的值增加 1，出现在 words 中的单词，每出现一次，相应的值减少 1。然后将窗口右移，右侧会加入一个单词，左侧会移出一个单词，并对 differ 做相应的更新。窗口移动时，若出现 differ 中值不为 0 的键的数量为 0，则表示这个窗口中的单词频次和 words 中单词频次相同，窗口的左端点是一个待求的起始位置。划分的方法有 n 种，做 n 次滑动窗口后，即可找到所有的起始位置。

作者：力扣官方题解
链接：https://leetcode.cn/problems/substring-with-concatenation-of-...
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
public:
    vector<int> findSubstring(string &s, vector<string> &words) {
        vector<int> res;
        int m = words.size(), n = words[0].size(), ls = s.size();
        for (int i = 0; i < n && i + m * n <= ls; ++i) {
            unordered_map<string, int> differ;
            for (int j = 0; j < m; ++j) {
                ++differ[s.substr(i + j * n, n)];
            }
            for (string &word: words) {
                if (--differ[word] == 0) {
                    differ.erase(word);
                }
            }
            for (int start = i; start < ls - m * n + 1; start += n) {
                if (start != i) {
                    string word = s.substr(start + (m - 1) * n, n);
                    if (++differ[word] == 0) {
                        differ.erase(word);
                    }
                    word = s.substr(start - n, n);
                    if (--differ[word] == 0) {
                        differ.erase(word);
                    }
                }
                if (differ.empty()) {
                    res.emplace_back(start);
                }
            }
        }
        return res;
    }
};

我希望通过测试例

Answer 1

你的代码中存在几个关键错误，导致它无法通过测试例。下面是你的代码中的一些问题以及修正建议：

1. 初始窗口的构建错误：

   • 你在代码中尝试通过 win[s.substr(k, m)]++; 来构建初始窗口，这是不正确的。这里 m 是 words 数组的长度，而 n 是每个单词的长度。因此，你应该使用 n 来提取单词，而不是 m。
   • 正确的做法是对 s 进行长度为 n 的划分，并为每个划分创建一个哈希表来跟踪单词的频率。

2. 滑动窗口的更新逻辑错误：

   • 你在滑动窗口时尝试删除和重新添加单词，但逻辑不正确。特别是 win.erase(s.substr(start + m * n, n)); 这行代码试图删除一个不在当前窗口内的单词，这是没有意义的。
   • 你需要正确地更新窗口内的单词频率，这通常涉及移入和移出一个单词。

3. 对哈希表的比较错误：

   • 你使用 if (wordsMap == win) 来比较两个哈希表，这在你的代码逻辑中是不正确的，因为 win 哈希表在滑动过程中没有正确更新。
   • 正确的做法是在每次窗口移动时检查哈希表是否为空，如果为空，则表示找到了一个匹配。

下面是修正后的代码，基于滑动窗口的方法：

#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        int m = words.size(), n = words[0].size(), ls = s.size();
        
        // 构建 words 中单词的频率哈希表
        unordered_map<string, int> wordsMap;
        for (const string& word : words) {
            wordsMap[word]++;
        }
        
        // 遍历 s 的所有可能的起始位置（每隔 n 个字符开始一个新的划分）
        for (int i = 0; i < n && i + m * n <= ls; ++i) {
            // 初始化当前窗口的单词频率哈希表
            unordered_map<string, int> differ;
            for (int j = 0; j < m; ++j) {
                string word = s.substr(i + j * n, n);
                differ[word]++;
            }
            
            // 根据 wordsMap 初始化 differ，将 words 中的单词频率减去
            for (const auto& pair : wordsMap) {
                if (--differ[pair.first] == 0) {
                    differ.erase(pair.first);
                }
            }
            
            // 滑动窗口，检查每个可能的起始位置
            for (int start = i; start <= ls - m * n; start += n) {
                if (start != i) {
                    // 移除窗口左侧的单词
                    string leftWord = s.substr(start - n, n);
                    if (++differ[leftWord] == 0) {
                        differ.erase(leftWord);
                    }
                    
                    // 移除窗口右侧的单词（注意这里已经是下一个窗口的左侧单词了，但在当前窗口是右侧的最后一个单词）
                    string rightWord = s.substr(start + (m - 1) * n, n);
                    if (--differ[rightWord] == 0) {
                        differ.erase(rightWord);
                    }
                }
                
                // 如果 differ 为空，说明当前窗口是一个匹配
                if (differ.empty()) {
                    res.push_back(start);
                }
            }
        }
        
        return res;
    }
};

这段代码使用了滑动窗口的方法，并且正确地构建了单词频率的哈希表，以及在滑动过程中正确地更新了哈希表。希望这能帮助你通过测试例。