LeetCode算法题-30. 串联所有单词的子串（Swift）
2019-10-20 本文已影响0人
entre_los_dos
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例 1：
输入：
s = "barfoothefoobarman",
words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
示例 2：
输入：
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
输出：[]
方法一：遍历每一位。很耗时。
func findSubstring(_ s: String, _ words: [String]) -> [Int] {
if words.count == 0 {
return []
}
let perWord = words.first!.count
if s.count < perWord * words.count {
return []
}
//找出所有words里面的单词作为key，个数作为value，存到字典里面
var wordsDic = [String: Int]()
for word in words {
let num = wordsDic[word]
wordsDic[word] = (num ?? 0) + 1
}
//存放结果的数组
var result = [Int]()
//遍历s字符串，创建新字典currentWordsDic存单词：个数。比较currentWordsDic和wordsDic个数
for i in 0...s.count - perWord * words.count {
var currentWordsDic = [String: Int]()
result.append(i)
for j in stride(from: i, to: i+perWord * words.count, by: perWord) {
let curStr = getCurrentStrin(s, j, j+perWord)
if (wordsDic[curStr] ?? 0) - (currentWordsDic[curStr] ?? 0) <= 0 {
result.removeLast()
break
}else {
currentWordsDic[curStr] = (currentWordsDic[curStr] ?? 0) + 1
}
}
}
return result
}
func getCurrentStrin(_ s: String, _ startIndex: Int, _ endIndex: Int) -> String {
let start = s.index(s.startIndex, offsetBy: startIndex)
let end = s.index(s.startIndex, offsetBy: endIndex)
return String(s[start..<end])
}
方法二：对方法一的优化。不需遍历每一位。会记住已经遍历过的单词。
func findSubstring(_ s: String, _ words: [String]) -> [Int] {
if words.count == 0 {
return []
}
let perWord = words.first!.count
if s.count < perWord * words.count {
return []
}
//找出所有words里面的单词作为key，个数作为value，存到字典里面
var wordsDic = [String: Int]()
for word in words {
let num = wordsDic[word]
wordsDic[word] = (num ?? 0) + 1
}
//存放结果的数组
var result = [Int]()
//遍历s字符串，创建新字典currentWordsDic存单词：个数。比较currentWordsDic和wordsDic个数
var i = 0
while i <= s.count - perWord * words.count && i < perWord {
var currentWordsDic = [String: Array<Int>]()//key:单词,value:数组index
var startIndex = i
var curIndex = startIndex
while startIndex <= s.count - perWord * words.count {
let curStr = getCurrentString(s, curIndex, curIndex+perWord)
if (wordsDic[curStr] ?? 0) == 0 {
//如果这个值不在原数组中
curIndex += perWord
startIndex = curIndex
currentWordsDic = [String: Array<Int>]()//key:单词,value:数组index
}else {
if (currentWordsDic[curStr] ?? []).count == 0 {
currentWordsDic[curStr] = [curIndex]
}else {
currentWordsDic[curStr]!.append(curIndex)
}
if wordsDic[curStr]! - (currentWordsDic[curStr] ?? []).count < 0 {
//如果这个值数量已经超出原数组，找出这个值的第一个index，并删除字典里面此index之前的数据，startIndex = 此index+3
let array = currentWordsDic[curStr]!
let index = array.first!
if index - startIndex < curIndex - (index + perWord) {
for j in startIndex...index {
let string = getCurrentString(s, j, j+perWord)
currentWordsDic[string]!.removeFirst()
}
}else {
currentWordsDic = [String: Array<Int>]()//key:单词,value:数组index
for j in (index + perWord)...curIndex {
let string = getCurrentString(s, j, j+perWord)
if (currentWordsDic[string] ?? []).count == 0 {
currentWordsDic[string] = [j]
}else {
currentWordsDic[string]!.append(j)
}
}
}
startIndex = index + perWord
curIndex += perWord
}else {
if curIndex + perWord - startIndex == perWord * words.count {
//如果遍历完数组，即找到了与数组单词适合的p子串
result.append(startIndex)
let stringStart = getCurrentString(s, startIndex, startIndex+perWord)
currentWordsDic[stringStart]?.removeFirst()
curIndex += perWord
startIndex += perWord
}else {
curIndex += perWord
}
}
}
}
i += 1
}
return result
}
func getCurrentString(_ s: String, _ startIndex: Int, _ endIndex: Int) -> String {
let start = s.index(s.startIndex, offsetBy: startIndex)
let end = s.index(s.startIndex, offsetBy: endIndex)
return String(s[start..<end])
}
大约3764ms
方法三：基于方法二的优化，将s换成Array(s)来取值
func findSubstring(_ s: String, _ words: [String]) -> [Int] {
if words.count == 0 {
return []
}
let perWord = words.first!.count
if s.count < perWord * words.count {
return []
}
//找出所有words里面的单词作为key，个数作为value，存到字典里面
var wordsDic = [String: Int]()
for word in words {
let num = wordsDic[word]
wordsDic[word] = (num ?? 0) + 1
}
let chars = Array(s)
//存放结果的数组
var result = [Int]()
//遍历s字符串，创建新字典currentWordsDic存单词：个数。比较currentWordsDic和wordsDic个数
var i = 0
while i <= chars.count - perWord * words.count && i < perWord {
var currentWordsDic = [String: Array<Int>]()//key:单词,value:数组index
var startIndex = i
var curIndex = startIndex
while startIndex <= s.count - perWord * words.count {
var curStr = ""
for k in curIndex..<curIndex+perWord {
curStr += String(chars[k])
}
if (wordsDic[curStr] ?? 0) == 0 {
//如果这个值不在原数组中
curIndex += perWord
startIndex = curIndex
currentWordsDic = [String: Array<Int>]()//key:单词,value:数组index
}else {
if (currentWordsDic[curStr] ?? []).count == 0 {
currentWordsDic[curStr] = [curIndex]
}else {
currentWordsDic[curStr]!.append(curIndex)
}
if wordsDic[curStr]! - (currentWordsDic[curStr] ?? []).count < 0 {
//如果这个值数量已经超出原数组，找出这个值的第一个index，并删除字典里面此index之前的数据，startIndex = 此index+3
let array = currentWordsDic[curStr]!
let index = array.first!
if index - startIndex < curIndex - (index + perWord) {
for j in startIndex...index {
var string = ""
for k in j..<j+perWord {
string += String(chars[k])
}
currentWordsDic[string]!.removeFirst()
}
}else {
currentWordsDic = [String: Array<Int>]()//key:单词,value:数组index
for j in (index + perWord)...curIndex {
var string = ""
for k in j..<j+perWord {
string += String(chars[k])
}
if (currentWordsDic[string] ?? []).count == 0 {
currentWordsDic[string] = [j]
}else {
currentWordsDic[string]!.append(j)
}
}
}
startIndex = index + perWord
curIndex += perWord
}else {
if curIndex + perWord - startIndex == perWord * words.count {
//如果遍历完数组，即找到了与数组单词适合的p子串
result.append(startIndex)
var stringStart = ""
for k in startIndex..<startIndex+perWord {
stringStart += String(chars[k])
}
currentWordsDic[stringStart]?.removeFirst()
curIndex += perWord
startIndex += perWord
}else {
curIndex += perWord
}
}
}
}
i += 1
}
return result
}
大约1756ms，相比于s[index..<index]取值来说，快了很多。
