串联所有单词的子串
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如，如果 words = [“ab”,“cd”,“ef”]， 那么 “abcdef”， “abefcd”，“cdabef”， “cdefab”，“efabcd”， 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
滑动窗口法+哈希表
记 words的长度为 m，words中每个单词的长度为 n，s 的长度为 ls。首先需要将 s 划分为单词组，每个单词的大小均为 n （首尾除外）。这样的划分方法有 n 种，即先删去前 i （i=0∼n−1）个字母后，将剩下的字母进行划分，如果末尾有不到 n 个字母也删去。
比较抽象，详细见代码部分，有详细备注。
复杂度分析：
时间复杂度：O(lsn)
空间复杂度：O(mn)
Swift
//滑动窗口法 + 哈希表
func findSubstring(_ s: String, _ words: [String]) -> [Int] {
var res:[Int] = [Int]()
let m = words.count, n = words[0].count, ls = s.count
// 开始对s切片，由于模式字符串长度为n，则n为一个周期切片就不会重复出现，且考虑到了所有不同的切片模式
for i in 0..<n {
//滑动窗口超过了总长度，则终止
if i + m * n > ls {
break
}
//用一个哈希表 differ表示窗口中单词频次和words中单词频次之差
var differ:[String: Int] = [String : Int]()
//滑动窗口所含单词数量为m个，个数加1
for j in 0..<m {
let str:String = String(s[s.index(s.startIndex, offsetBy: i+j*n)..<s.index(s.startIndex, offsetBy: i+(j+1)*n)])
differ[str] = (differ[str] ?? 0)+1;
}
//words中存在的单词个数减1
for word in words {
differ[word] = (differ[word] ?? 0)-1;
if differ[word] == 0 {
differ.removeValue(forKey: word)
}
}
//以n为步进值，滑动窗口开始判断
var start = i
while start < (ls - m * n + 1 ) {
if start != i {
//右侧增加的一个字符串计数值加1
var str:String = String(s[s.index(s.startIndex, offsetBy: start+(m-1)*n)..<s.index(s.startIndex, offsetBy: start+m*n)])
differ[str] = (differ[str] ?? 0) + 1;
if differ[str] == 0 {
differ.removeValue(forKey: str)
}
//左侧移出去的字符串计数值减1
str = String(s[s.index(s.startIndex, offsetBy: start-n)..<s.index(s.startIndex, offsetBy: start)])
differ[str] = (differ[str] ?? 0) - 1;
if differ[str] == 0 {
differ.removeValue(forKey: str)
}
}
//窗口中单词频次和words中单词频次之差为0表示配对到了
if differ.isEmpty {
res.append(start)
}
start += n
}
}
return res
}
OC
//滑动窗口法 + 哈希表
- (NSArray *)findSubstring:(NSString *)s words: (NSArray <NSString *>*)words {
NSInteger m = words.count, n = words[0].length, ls = s.length;
NSMutableArray *res = [NSMutableArray array];
// 开始对s切片，由于模式字符串长度为n，则n为一个周期切片就不会重复出现，且考虑到了所有不同的切片模式
for (NSInteger i=0; i<n; i++) {
if (i + m * n > ls) {
//滑动窗口超过了总长度，则终止
break;
}
//用一个哈希表 differ表示窗口中单词频次和words中单词频次之差
NSMutableDictionary *differ = [NSMutableDictionary dictionary];
//将当前滑动窗口里的字符串计数值加1
for (NSInteger j=0; j<m; j++) {
NSString *word = [s substringWithRange:NSMakeRange(i+j*n, n)];
differ[word] = @([differ[word] integerValue] + 1);
}
//将words中存在字符串计数值减1
for (NSString *word in words) {
differ[word] = @([differ[word] integerValue] - 1);
if ([differ[word] integerValue] == 0) {
[differ removeObjectForKey:word];
}
}
//开始滑动窗口比对,以n为步进值
for (NSInteger start = i; start < ls-m*n+1 ; start+=n) {
if (start != i) {
//右侧增加的一个字符串计数值加1
NSString *word = [s substringWithRange:NSMakeRange(start+(m-1)*n, n)];
differ[word] = @([differ[word] integerValue] + 1);
if ([differ[word] integerValue] == 0) {
[differ removeObjectForKey:word];
}
//左侧移出去的字符串计数值减1
word = [s substringWithRange:NSMakeRange(start-n, n)];
differ[word] = @([differ[word] integerValue] - 1);
if ([differ[word] integerValue] == 0) {
[differ removeObjectForKey:word];
}
}
//窗口中单词频次和words中单词频次之差为0表示配对到了
if (differ.allKeys.count == 0) {
[res addObject:@(start)];
}
}
}
return res;
}
