引言
题目链接：https://leetcode.com/problems/substring-with-concatenation-of-all-words/
题目大意
给出一个长字符串s和一个字符串数组words，返回由words中字符串拼接成的长字符串（假设为x）在s中的索引集合（x由words中所有元素拼接而成，每一个元素都包含且只有一个）
- Example
|
1 2 3 4 5 6 7 8 9 10 11 |
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++版本
|
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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
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版本
|
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 35 36 37 38 39 40 41 |
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 } |
