题目描述
题目链接:30. Substring with Concatenation of All Words
You are given a string
s
and an array of stringswords
of the same length. Return all starting indices of substring(s) ins
that is a concatenation of each word inwords
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()
即可
代码如下:
#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