題目
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
Example 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.
Example 2:
Input:
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
Output: []
給出一個字符串 s ，和一個單詞數(shù)組 words，words 中所有的單詞長度相同底扳，找出 s 中仅偎，由 words 所有單詞拼接而成的子串的起始索引摄杂。
解題思路
因為 words 中所有的單詞長度是相同的，所以可以考慮以固定的單詞長度為切割，遍歷比較每個單詞：
- 用 words 創(chuàng)建 map，key 為單詞昂验，value 為單詞的數(shù)量。
- s 長度 sLen，單詞個數(shù) wCount既琴，單詞長度 wLen占婉，存儲結(jié)果數(shù)組 result。
- 由于是遍歷比較單詞甫恩，所以兩層遍歷逆济，外層的遍歷 i 是 0 到 wLen-1，里層遍歷 j 為 i 到 sLen-wLen磺箕，每次增長 wLen奖慌。
- 外層遍歷：將 left 索引移動到 i ，總匹配成功單詞數(shù)量 count = 0滞磺，創(chuàng)建單詞匹配池 pairPool升薯，key 為單詞，匹配數(shù)量 value 為 0 击困。
- 里層遍歷：
- 獲取 s 中的單詞 subStr涎劈，若匹配成功，則 pairPool 中對應(yīng)匹配數(shù)量 +1阅茶，總匹配成功單詞數(shù)量 +1
- 匹配成功之后蛛枚，如果 subStr 匹配成功數(shù)量大于 words 中的數(shù)量，則說明 subStr 匹配過多脸哀，需要從 left 開始逐一拋棄單詞蹦浦，直至subStr 匹配數(shù)量與 words 中的數(shù)量一致
- 如果 總匹配成功單詞數(shù)量 count 等于 wCount，則說明在該次比較中撞蜂，words 的所有單詞均匹配成功盲镶，left 即為一個結(jié)果，將 left 加入到 result中蝌诡，count -1溉贿，left 右移 wLen
- 如果 subStr 匹配失敗，則拋棄之前的匹配數(shù)據(jù)浦旱，重置 pairPool宇色、count，將left 重置到 j + wLen處
- 兩層遍歷結(jié)束后颁湖，返回結(jié)果 result
代碼實現(xiàn)
func findSubstring(_ s: String, _ words: [String]) -> [Int] {
//如果 s 或者 words 為空宣蠕，則返回 []
if s.isEmpty || words.count<=0 {
return []
}
//聲明 s 長度 sLen，單詞個數(shù) wCount甥捺，單詞長度 wLen
let sLen = s.count, wCount = words.count, wLen = words.first!.count
//聲明 result 存儲結(jié)果用
var result = [Int]()
// map 用于存儲 words 中每個單詞的個數(shù)
var map = [String:Int]()
// pairPool1 用于重新初始化匹配單詞池
var pairPool1 = [String:Int]()
// 配置 map 和 pairPool1
for word in words {
if map.keys.contains(word) {
map[word]! += 1
}else{
map[word] = 1
pairPool1[word] = 0
}
}
// 遍歷從 0 到 wLen-1
for i in 0 ..< wLen {
// left 為目標子串的左索引抢蚀， count 為已經(jīng)匹配成功的單詞個數(shù)
var left = i, count = 0
//將pairPool1 復(fù)制給 pairPool 進行初始化，pairPool 用以存儲每個單詞已經(jīng)匹配的個數(shù)
var pairPool = pairPool1
// 從 i 開始涎永，wlen 為長度思币，sLen=wLen 為尾鹿响，遍歷每個單詞
for j in stride(from: i, through: sLen-wLen, by: wLen) {
//獲取 s 中 j 索引處的單詞 subStr
let jIndex = s.index(s.startIndex, offsetBy: j)
let subStr = String(s[jIndex ..< s.index(jIndex, offsetBy: wLen)])
//如果 words 中含有該單詞羡微，則單詞匹配成功
if map.keys.contains(subStr) {
//單詞匹配成功谷饿，在匹配池中，subStr 的匹配數(shù)量 +1 妈倔，總匹配數(shù)量 count +1
pairPool[subStr]! += 1
count += 1
//如果 s 中 subStr 匹配數(shù)量大于 words 中的數(shù)量博投，則從 left 開始逐一拋棄單詞
//直至 s 中 subStr 匹配數(shù)量等于 words 中的數(shù)量
while pairPool[subStr]! > map[subStr]! {
//獲取 left 索引處單詞 lSubStr
let lIndex = s.index(s.startIndex, offsetBy: left)
let lSubStr = String(s[lIndex ..< s.index(lIndex, offsetBy: wLen)])
// lSubStr 匹配成功數(shù)量 -1
pairPool[lSubStr]! -= 1
//總匹配成功單詞數(shù)量 count -1
count -= 1
// left 右移 wLen 位
left += wLen
}
//如果 count 等于 wCount，則說明在該次比較中盯蝴，words 的所有單詞均匹配成功毅哗，left 即為一個結(jié)果
if count == wCount {
// words 中所有單詞匹配成功，將結(jié)果 left 添加到 result 中
result.append(left)
//獲取 left 索引處單詞 lSubStr
let lIndex = s.index(s.startIndex, offsetBy: left)
let lSubStr = String(s[lIndex ..< s.index(lIndex, offsetBy: wLen)])
// lSubStr 匹配成功數(shù)量 -1
pairPool[lSubStr]! -= 1
//總匹配成功單詞數(shù)量 count -1
count -= 1
// left 右移 wLen 位
left += wLen
}
}else{
//若 words 中沒有該單詞捧挺，則說明匹配失敗，拋棄之前的匹配數(shù)據(jù)，重置 pairPool邑滨、count捷泞，將left 重置到 j + wLen處
pairPool = pairPool1
count = 0
left = j + wLen
}
}
}
//返回結(jié)果
return result
}
