0%

[Leetcode]30. Substring with Concatenation of All Words(C++)

题目描述

题目链接: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,但是如果只是要通过的话思路还是比较容易想到的。通过题意可以以下思路:

  • 首先通过哈希表 recordwords 中每个单词的出现次数进行记录
  • 检查 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