题目描述

题目链接：30. Substring with Concatenation of All Words

You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.

You can return the answer in any order.

例子

例子 1

Input: s = “barfoothefoobarman”, words = [“foo”,”bar”]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are “barfoo” and “foobar” respectively.
The output order does not matter, returning [9,0] is fine too.

例子 2

Input: s = “wordgoodgoodgoodbestword”, words = [“word”,”good”,”best”,”word”]
Output: []

例子 3

Input: s = “barfoofoobarthefoobarman”, words = [“bar”,”foo”,”the”]
Output: [6,9,12]

Follow Up

Note

Constraints

• 1 <= s.length <= 10^4
• s consists of lower-case English letters.
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] consists of lower-case English letters.

解题思路

虽然这道题标记是 Hard，但是如果只是要通过的话思路还是比较容易想到的。通过题意可以以下思路：

• 首先通过哈希表 record 对 words 中每个单词的出现次数进行记录
• 检查 s 中所有长度 words.size() * words[0].length() 的子串 （用滑动窗口）
• 对每一个滑动窗口也建立一个哈希表 cur_record 中按照 words[0].length() 为步长进行遍历取词 word，对每一个 word 进行检查，如果 cur_record[word] > record[word] 则表示出现了不在 words 中的单词直接跳出即可
• 如果中间一直没有跳出直到滑动窗口的末尾自然退出循环，则表示所有 word 都在 words 里，将当前起始坐标添加至结果中

注意：

• 首先判断 s.length() >= words.size() * words[0].length()，如果不满足可以直接返回空集
• 遍历 s 的时候也不必遍历到末尾，直到 s.length() - words.size() * words[0].length() 即可

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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

class Solution {
public:
    std::vector<int> findSubstring(std::string s, std::vector<std::string>& words) {
        std::vector<int> inds;

        if (words.empty()) return {};
        int len = words[0].length();
        if (s.length() < words.size() * len) return {};

        std::unordered_map<std::string, int> records;
        for (const std::string& word: words) {
            records[word]++;
        }

        for (int i = 0; i <= s.length() - len * words.size(); i++) {
            std::unordered_map<std::string, int> current_records;
            int count = 0;
            for (; count < words.size(); count++) {
                std::string word = s.substr(i + count * len, len);
                current_records[word]++;
                if (current_records[word] > records[word]) break;
            }

            if (count == words.size()) inds.push_back(i);
        }

        return inds;

    }
};

• 时间复杂度: O(mn)
• 空间复杂度: O(n)

GitHub 代码同步地址： 30.SubstringWithConcatenationOfAllWords.cpp

其他题目：
GitHub: Leetcode-C++-Solution
博客： Leetcode-Solutions