题目描述
题目链接: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()
即可
代码如下:
1 |
|
- 时间复杂度: O(mn)
- 空间复杂度: O(n)
GitHub 代码同步地址: 30.SubstringWithConcatenationOfAllWords.cpp
其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions