一、题目
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例 1：
输入：
s = "barfoothefoobarman",
words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoor" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
示例 2：
输入：
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
输出：[]
二、解题
将字符串(s)分成单词长度(wordLength)种分割方式。
例如示例1:
s="barfoothefoobarman"; words = ["foo","bar"]; wordLength=3;
m1=["foo":1,"bar":1];
组合1：["bar","foo","the","foo","bar","man"]
组合2：["b","arf","oot","hef","oob","arm","an"]
组合3：["ba","rfo","oth","efo","oba","rma","n"]
之后分别处理这三种情况。针对组合的处理见代码实现注释。
时间复杂度为O(m)。n为s的长度,m为words.count。
有两个for循环，第一个for循环为m，第二个for循环为n/m，所以和起来复杂度为O(n)。
三、代码实现
class Solution {
func findSubstring(_ s: String, _ words: [String]) -> [Int] {
if s.isEmpty || words.isEmpty {
return []
}
let wordLength = words[0].count
var resultARR = [Int]()
var m1 = [String: Int]()
// 将words存入m1中,key为word,value为word在words出现的个数
for word in words {
if m1[word] != nil {
m1[word]! += 1
}else {
m1[word] = 1
}
}
// 遍历wordLength的原因是s的组合方式有wordLength中
// s="12345678" wordLength=3
// 组合一 "123", "456", "78"
// 组合二 "1", "234", "567", "8"
// 组合三 "12", "345", "678"
for i in 0..<wordLength {
var left = i
// 记录匹配到的word的总数
var count = 0
// 记录匹配到的word各自的数量
var m2 = [String : Int]()
// 以i为起点,wordLength为步长,s.count-wordLength+1为终点,遍历
for j in stride(from: i,to: s.count - wordLength + 1, by: wordLength) {
// 取出单词t
let t = subString(s, j, wordLength)
// 判断t是否在m1中
if m1.keys.contains(t) {
// t存在在m1中,使用m2记录数量
if m2[t] != nil {
m2[t]! += 1
}else {
m2[t] = 1
}
// 如果m2中t的数量小于等于m1中t的数量说明匹配正确
if m2[t]! <= m1[t]! {
count += 1
}else {// 反之,说明匹配多了,left不符合要求,需要清除之前不符合条件的word
while(m2[t]! > m1[t]!) {
// 从第left开始往后清理
let t1 = subString(s, left, wordLength)
m2[t1]! -= 1
// 这里的判断是为了区分word重复的情况,当word重复时m2[t1]! == m1[t1]!时,不需要count-1
if m2[t1]! < m1[t1]! {
count -= 1
}
left += wordLength
}
}
// 当count == words.count说明left符合条件,将left添加到最后结果中,并将left向后移动
if count == words.count {
resultARR.append(left)
m2[subString(s, left, wordLength)]! -= 1
count -= 1
left += wordLength
}
}else {// 没有找到t,说明匹配中断,需重新处理,并将left向后移动
m2.removeAll()
count = 0
left = j + wordLength
}
}
}
return resultARR
}
func subString(_ s: String, _ loc : Int, _ len : Int) -> String {
return (s as NSString).substring(with: NSRange(location: loc, length: len))
}
}
Demo地址：github
