题目
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 ，和一个单词数组 words，words 中所有的单词长度相同，找出 s 中，由 words 所有单词拼接而成的子串的起始索引。
解题思路
因为 words 中所有的单词长度是相同的，所以可以考虑以固定的单词长度为切割，遍历比较每个单词：
- 用 words 创建 map，key 为单词，value 为单词的数量。
- s 长度 sLen，单词个数 wCount，单词长度 wLen，存储结果数组 result。
- 由于是遍历比较单词，所以两层遍历，外层的遍历 i 是 0 到 wLen-1，里层遍历 j 为 i 到 sLen-wLen，每次增长 wLen。
- 外层遍历：将 left 索引移动到 i ，总匹配成功单词数量 count = 0，创建单词匹配池 pairPool，key 为单词，匹配数量 value 为 0 。
- 里层遍历：
- 获取 s 中的单词 subStr，若匹配成功，则 pairPool 中对应匹配数量 +1，总匹配成功单词数量 +1
- 匹配成功之后，如果 subStr 匹配成功数量大于 words 中的数量，则说明 subStr 匹配过多，需要从 left 开始逐一抛弃单词，直至subStr 匹配数量与 words 中的数量一致
- 如果 总匹配成功单词数量 count 等于 wCount，则说明在该次比较中，words 的所有单词均匹配成功，left 即为一个结果，将 left 加入到 result中，count -1，left 右移 wLen
- 如果 subStr 匹配失败，则抛弃之前的匹配数据，重置 pairPool、count，将left 重置到 j + wLen处
- 两层遍历结束后，返回结果 result
代码实现
func findSubstring(_ s: String, _ words: [String]) -> [Int] {
//如果 s 或者 words 为空，则返回 []
if s.isEmpty || words.count<=0 {
return []
}
//声明 s 长度 sLen，单词个数 wCount，单词长度 wLen
let sLen = s.count, wCount = words.count, wLen = words.first!.count
//声明 result 存储结果用
var result = [Int]()
// map 用于存储 words 中每个单词的个数
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 为已经匹配成功的单词个数
var left = i, count = 0
//将pairPool1 复制给 pairPool 进行初始化，pairPool 用以存储每个单词已经匹配的个数
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 的匹配数量 +1 ，总匹配数量 count +1
pairPool[subStr]! += 1
count += 1
//如果 s 中 subStr 匹配数量大于 words 中的数量，则从 left 开始逐一抛弃单词
//直至 s 中 subStr 匹配数量等于 words 中的数量
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 匹配成功数量 -1
pairPool[lSubStr]! -= 1
//总匹配成功单词数量 count -1
count -= 1
// left 右移 wLen 位
left += wLen
}
//如果 count 等于 wCount，则说明在该次比较中，words 的所有单词均匹配成功，left 即为一个结果
if count == wCount {
// words 中所有单词匹配成功，将结果 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 匹配成功数量 -1
pairPool[lSubStr]! -= 1
//总匹配成功单词数量 count -1
count -= 1
// left 右移 wLen 位
left += wLen
}
}else{
//若 words 中没有该单词，则说明匹配失败，抛弃之前的匹配数据，重置 pairPool、count，将left 重置到 j + wLen处
pairPool = pairPool1
count = 0
left = j + wLen
}
}
}
//返回结果
return result
}
网友评论