# 引言
题目链接：https://leetcode.com/problems/substring-with-concatenation-of-all-words/
# 题目大意
给出一个长字符串 s 和一个字符串数组 words, 返回由 words 中字符串拼接成的长字符串 (假设为 x) 在 s 中的索引集合 (x 由 words 中所有元素拼接而成，每一个元素都包含且只有一个)
- Example
Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
Input:
s = "wordgoodgoodgoodbestword"
words = ["word","good","best","good"]
Output: [8]
# 题解
这个题目其实和 LeetCode 的第三题 Substring Without Repeating Characters 的解题思路核心是一样的，可以看看博主之前的题解 传送门 Click Here! 都是利用滑动窗口的思想。
来分析下两道题题目的区别，第三题求的是连续的最长的不包含重复字符的子串长度，这道题目求解由 words 中字符串拼接成的长字符串 x 在 s 中的索引位置集合。转换一下，就是 s 中查找连续的一段字符串 x, 这个字符串由 words 中所有字符串拼接而成，把所有符合条件的索引记录返回即可。 所以两者本质上是一致的。
由于本题 words 中所有字符串长度一致 (假设为 len), 所以可以把 len 当做一个整体。设定滑动窗口包含的子串由 words 中单词拼接而成 (当前从某个起点开始正在查询并且不断扩展的子串), 采取如下步骤解题
- 申明一个 hashmap, 用 words 中的字符串作为 key 在 words 中出现次数作为 value, 构建比对映射表。
- 设定当前滑动窗口左边界 lastDiffIndex, 初始为 0
- 申明一个 curhashmap 表示已经匹配查询列表，查询长度为 len 的子串 sub 在 hashmap 中是否存在
- 不存在：表明当前滑动窗口不符合规范，不能由 words 中所有字符串凭拼接构成，直接设置滑动窗口左边界为当前下标
- 存在：(1) curhashmap 中的键值对对应数量小于 hashmap 查询子串有效，滑动窗口左边界不变对应 curhashmap 对应键值数量加一，继续查询下一个长度为 len 的子串 sub, (2) curhashmap 中的键值对对应数量大于等于 hashmap 查询子串，无效，移动滑动窗口左边界每次加 len 的跨度，知道当前查询子串 sub 对应键值数量小于等于 hashmap
这样可以做到每次跨度为 words 中单个字符串长度 len, 为了能够遍历到所有单词组合，一般来说会选择双层循环外层每次 + 1 再次遍历，但是本题 words 中字符串长度一致，每次跨度都是 len, 所以只需要 + 1 往后偏移 len-1 次进行跨度为 len 的完全遍历即可覆盖 s 中的所有字符，因为再次偏移到 len 实际上已经进入了下一个周期循环完全重复。
因此本题采用双层循环，外层 i = [0-len] 跨度为 1, 内层 j = [i, lens-len] 跨度为 len, 每次截取长度为 [j,j+len] 之间的字符串判断，总遍历次数 为 len*n/len=n
# 复杂度
时间复杂度 O(n)
空间复杂度 O(km) , k 为给出的单词序列的长度，m 为序列中每个单词的长度
# AC 代码
c++ 版本
class Solution | |
{ | |
public: | |
vector<int> findSubstring(string s, vector<string> &words) | |
{ | |
// invalid | |
if (s.length() <= 0 || words.size() <= 0) | |
{ | |
return vector<int>{}; | |
} | |
unordered_map<string, int> hashMap; | |
unordered_map<string, int> curhashxMap; | |
vector<int> ret; | |
for (string word : words) | |
{ | |
++hashMap[word]; | |
} | |
int lenS = s.length(); | |
int lenWord = words[0].length(); | |
int lens = words.size(); | |
int lastDiffIndex = 0; | |
int count = 0; | |
for (int i = 0; i < lenWord; ++i) | |
{ | |
curhashxMap.clear(); | |
lastDiffIndex = i; | |
count = 0; | |
for (int j = i; j <= lenS - lenWord; j += lenWord) | |
{ | |
string tmp = s.substr(j, lenWord); | |
if (hashMap.count(tmp) <= 0) | |
{ | |
curhashxMap.clear(); | |
lastDiffIndex = j + lenWord; | |
count = 0; | |
continue; | |
} | |
++curhashxMap[tmp]; | |
++count; | |
if (curhashxMap[tmp] <= hashMap[tmp]) | |
{ | |
if (lens == count) | |
{ | |
ret.push_back(lastDiffIndex); | |
--curhashxMap[s.substr(lastDiffIndex, lenWord)]; | |
--count; | |
lastDiffIndex += lenWord; | |
} | |
} | |
else | |
{ | |
while (curhashxMap[tmp] > hashMap[tmp]) | |
{ | |
--curhashxMap[s.substr(lastDiffIndex, lenWord)]; | |
--count; | |
lastDiffIndex += lenWord; | |
} | |
} | |
} | |
} | |
return ret; | |
} | |
}; |
go 版本
func findSubstring(s string, words []string) []int { | |
lenS, lenWords := len(s), len(words) | |
if 0 == lenS || 0 == lenWords { | |
return nil | |
} | |
hashMap, curHashMap := make(map[string]int), make(map[string]int) | |
var ret []int | |
lenword := len(words[0]) | |
for _, v := range words { | |
hashMap[v]++ | |
} | |
for i := 0; i < lenword; i++ { | |
curHashMap = make(map[string]int) | |
lastDiffIndex, count := i, 0 | |
for j := i; j <= lenS-lenword; j += lenword { | |
tmp := s[j : j+lenword] | |
if _, ok := hashMap[tmp]; false == ok { | |
curHashMap = make(map[string]int) | |
lastDiffIndex, count = j+lenword, 0 | |
continue | |
} | |
curHashMap[tmp]++ | |
count++ | |
if curHashMap[tmp] <= hashMap[tmp] { | |
if lenWords == count { | |
ret = append(ret, lastDiffIndex) | |
curHashMap[s[lastDiffIndex:lastDiffIndex+lenword]]-- | |
count-- | |
lastDiffIndex += lenword | |
} | |
} else { | |
for curHashMap[tmp] > hashMap[tmp] { | |
curHashMap[s[lastDiffIndex:lastDiffIndex+lenword]]-- | |
count-- | |
lastDiffIndex += lenword | |
} | |
} | |
} | |
} | |
return ret | |
} |
