來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
題目
給定一個(gè)字符串 s 和一些長(zhǎng)度相同的單詞 words。找出 s 中恰好可以由 words 中所有單詞串聯(lián)形成的子串的起始位置。
注意子串要與 words 中的單詞完全匹配，中間不能有其他字符，但不需要考慮 words 中單詞串聯(lián)的順序。
示例 1：
輸入：
s = "barfoothefoobarman",
words = ["foo","bar"]
輸出：[0,9]
解釋：
從索引 0 和 9 開始的子串分別是 "barfoo" 和 "foobar" 。
輸出的順序不重要, [9,0] 也是有效答案。
示例 2：
輸入：
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
輸出：[]
方法一：遍歷每一位。很耗時(shí)。
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，個(gè)數(shù)作為value，存到字典里面
var wordsDic = [String: Int]()
for word in words {
let num = wordsDic[word]
wordsDic[word] = (num ?? 0) + 1
}
//存放結(jié)果的數(shù)組
var result = [Int]()
//遍歷s字符串，創(chuàng)建新字典currentWordsDic存單詞：個(gè)數(shù)。比較currentWordsDic和wordsDic個(gè)數(shù)
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])
}
方法二：對(duì)方法一的優(yōu)化。不需遍歷每一位。會(huì)記住已經(jīng)遍歷過的單詞。
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，個(gè)數(shù)作為value，存到字典里面
var wordsDic = [String: Int]()
for word in words {
let num = wordsDic[word]
wordsDic[word] = (num ?? 0) + 1
}
//存放結(jié)果的數(shù)組
var result = [Int]()
//遍歷s字符串，創(chuàng)建新字典currentWordsDic存單詞：個(gè)數(shù)。比較currentWordsDic和wordsDic個(gè)數(shù)
var i = 0
while i <= s.count - perWord * words.count && i < perWord {
var currentWordsDic = [String: Array<Int>]()//key:單詞,value:數(shù)組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 {
//如果這個(gè)值不在原數(shù)組中
curIndex += perWord
startIndex = curIndex
currentWordsDic = [String: Array<Int>]()//key:單詞,value:數(shù)組index
}else {
if (currentWordsDic[curStr] ?? []).count == 0 {
currentWordsDic[curStr] = [curIndex]
}else {
currentWordsDic[curStr]!.append(curIndex)
}
if wordsDic[curStr]! - (currentWordsDic[curStr] ?? []).count < 0 {
//如果這個(gè)值數(shù)量已經(jīng)超出原數(shù)組，找出這個(gè)值的第一個(gè)index，并刪除字典里面此index之前的數(shù)據(jù)，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:數(shù)組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 {
//如果遍歷完數(shù)組，即找到了與數(shù)組單詞適合的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
方法三：基于方法二的優(yōu)化，將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，個(gè)數(shù)作為value，存到字典里面
var wordsDic = [String: Int]()
for word in words {
let num = wordsDic[word]
wordsDic[word] = (num ?? 0) + 1
}
let chars = Array(s)
//存放結(jié)果的數(shù)組
var result = [Int]()
//遍歷s字符串，創(chuàng)建新字典currentWordsDic存單詞：個(gè)數(shù)。比較currentWordsDic和wordsDic個(gè)數(shù)
var i = 0
while i <= chars.count - perWord * words.count && i < perWord {
var currentWordsDic = [String: Array<Int>]()//key:單詞,value:數(shù)組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 {
//如果這個(gè)值不在原數(shù)組中
curIndex += perWord
startIndex = curIndex
currentWordsDic = [String: Array<Int>]()//key:單詞,value:數(shù)組index
}else {
if (currentWordsDic[curStr] ?? []).count == 0 {
currentWordsDic[curStr] = [curIndex]
}else {
currentWordsDic[curStr]!.append(curIndex)
}
if wordsDic[curStr]! - (currentWordsDic[curStr] ?? []).count < 0 {
//如果這個(gè)值數(shù)量已經(jīng)超出原數(shù)組，找出這個(gè)值的第一個(gè)index，并刪除字典里面此index之前的數(shù)據(jù)，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:數(shù)組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 {
//如果遍歷完數(shù)組，即找到了與數(shù)組單詞適合的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]取值來說，快了很多。
