Leetcode题上的耗时题（30.所有单词串联的子串）

Question

我正在解决 leetcode 中的问题并遇到了 30.Substring with Concatenation of All Words 中的问题。

给定一个字符串 s 和一个字符串words 数组。所有单词串的长度都相同。

连接字符串是精确包含任何连接的单词排列的所有字符串的字符串。

例如，如果words = ["ab","cd","ef"]，则"abcdef"、"abefcd"、"cdabef"、"cdefab"、"efabcd"和"efcdab"都是连接字符串。 “acdbef”不是连接字符串，因为它不是任何单词排列的连接。

返回 s 中所有连接子字符串的起始索引的数组。您可以按任意顺序返回答案。

我的代码（C++）提交总是失败：

class SubstringWithConcatenationOfAllWords
{
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        
        size_t word_len = words[0].size();
        size_t words_size = words.size();
        vector<int> positions;

        if (s.size() < words_size * word_len) return positions;

        unordered_map<string, int> appear_map;

        for (string w : words) {
            appear_map[w]++;
        }

        for (int i = 0; i <= s.size() - words_size * word_len; i++) {
            //buffer = words;
            unordered_map<string, int> appear_map2;
            appear_map2 = appear_map;
            int j;
            for (j = 0; j < words_size; j++) {
                string subs = s.substr(i + j * word_len, word_len);
                if (appear_map2.count(subs) == 0) break; 
                if (appear_map2[subs] > 0) { 
                    appear_map2[subs]--;
                }
                else break; 
                /*auto it = find(buffer.begin(), buffer.end(), subs);
                if (it != buffer.end()) {
                    buffer.erase(it);
                }
                else break;
            }
            if (j==words_size) { 
                positions.push_back(i);
            }
        }
        return positions;
    }
};

测试用例 180/181 的失败是超出时间限制：字符串是“aaaaaa....aaaa”（这里有很多 a），单词是 [“a”, “a”, ..... , “a ”，“a”]（这里有很多“a”）。 我搜索了一个通过所有测试用例的良好解决方案代码示例，即：

class Solution {
    std::unordered_map<std::string, unsigned int> map;
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        std::vector<int> result;
        unsigned int length = words[0].size();

        map.clear();
        for (const std::string& word : words)
            map[word]++;

        for (unsigned int offset = 0; offset < length; ++offset) {
            unsigned int size = 0;
            std::unordered_map<std::string, unsigned int> seen;
            for (unsigned int i = offset; i + length <= s.size(); i += length) {
                std::string sub = s.substr(i, length);

                auto itr = map.find(sub);
                if (itr == map.end()) {
                    seen.clear();
                    size = 0;
                    continue;
                }

                ++seen[sub];
                ++size;
                while (seen[sub] > itr->second) {
                    std::string first = s.substr(i - (size - 1) * length, length);
                    --seen[first];
                    --size;
                }
                
                if (size == words.size())
                    result.push_back(i - (size - 1) * length);
            }
        }

        return result;
    }
};

我想弄清楚为什么我的代码在这个测试用例中解决问题的速度要慢得多。我试图从循环结构中找到原因，但我发现两个外部 for 循环看起来相同，并且我的代码在内部 for 循环内没有 while 循环。 Unorder_map.count() 并不比 unordered_map.find() 慢。我觉得我的时间复杂度也是 O(n*m)，其中 n 是字符串 s 的长度，m 是向量单词的大小。

谁能帮助我了解他做了哪些最佳操作才能使时间消耗比我快得多？

Answer 1

您的解决方案实际上是

O((s.size() - words_size * word_len) * words_size * word_len)

。它本质上是对匹配子字符串的每个可能的开始进行暴力破解，而不尝试重用任何先前计算的结果。这是有问题的，因为

words_size

可能高达

5000

。

通过的解决方案使用滑动窗口，以便内部循环在字符串的长度上呈线性（每个大小为

word_len

的子字符串最多在映射中添加和删除一次）。总时间复杂度为

O(word_len * s.size())

。单个单词的长度最多为

30

，所以这是相当高效的。