客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ 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:
Example 2: Input:
s = "wordgoodstudentgoodword",
words = ["word","student"]
Output:
给定一个字符串 s 和一些长度相同的单词 words。在 s 中找出可以恰好串联 words 中所有单词的子串的起始位置。 注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。 示例 1: 输入:
s = "barfoothefoobarman",
words = ["foo","bar"]
输出:
示例 2: 输入:
s = "wordgoodstudentgoodword",
words = ["word","student"]
输出:
304ms 1 class Solution { 2 func findSubstring(_ s: String, _ words: [String]) -> [Int] { 3 guard !words.isEmpty else { 4 return [] 5 } 6 guard !s.isEmpty else { 7 return words.contains("") ? [0] : [] 8 } 9 10 let string = Array(s) 11 let wordLength = words[0].count 12 let totalWordLength = words.count * wordLength 13 14 guard totalWordLength <= string.count else { 15 return [] 16 } 17 18 let originalWordToCount = words.reduce(into: [:], { $0[$1, default:0] += 1 }) 19 20 var startingIndices: [Int] = [] 21 22 for i in 0..<wordLength { 23 24 var startIndex = i 25 var wordToCount = originalWordToCount 26 27 for j in stride(from: i, to: string.count-wordLength+1, by: wordLength) { 28 29 let word = String(string[j..<(j+wordLength)]) 30 31 if let originalCount = originalWordToCount[word] { 32 33 while wordToCount[word] == nil { 34 let startWord = String(string[startIndex..<(startIndex+wordLength)]) 35 wordToCount[startWord, default: 0] += 1 36 startIndex += wordLength 37 } 38 39 if let currentCount = wordToCount[word] { 40 if currentCount == 1 { 41 wordToCount[word] = nil 42 } else { 43 wordToCount[word] = currentCount - 1 44 } 45 } 46 47 if wordToCount.isEmpty { 48 startingIndices.append(startIndex) 49 50 let startWord = String(string[startIndex..<(startIndex+wordLength)]) 51 wordToCount[startWord, default: 0] += 1 52 startIndex += wordLength 53 } 54 55 } else { 56 // reset 57 startIndex = j+wordLength 58 wordToCount = originalWordToCount 59 } 60 } 61 } 62 63 return startingIndices 64 } 65 } 312ms 1 class Solution { 2 func findSubstring(_ s: String, _ words: [String]) -> [Int] { 3 guard !words.isEmpty else { 4 return [] 5 } 6 guard !s.isEmpty else { 7 return words.contains("") ? [0] : [] 8 } 9 10 let string = Array(s) 11 12 let wordLength = words[0].count 13 let totalWordLength = words.count * wordLength 14 15 guard string.count >= totalWordLength else { 16 return [] 17 } 18 19 let originalWordToCount = words.reduce(into: [:], { $0[$1, default: 0] += 1 }) 20 21 var startingIndices: [Int] = [] 22 23 for i in 0..<wordLength { 24 25 var startIndex = i 26 var wordToCount: [String:Int] = [:] 27 var wordCount = 0 28 29 for j in stride(from: i, to: string.count - wordLength + 1, by: wordLength) { 30 31 let word = String(string[j..<(j+wordLength)]) 32 33 if let originalCount = originalWordToCount[word] { 34 35 wordToCount[word, default: 0] += 1 36 wordCount += 1 37 38 while let count = wordToCount[word], count > originalCount { 39 let startWord = String(string[startIndex..<(startIndex+wordLength)]) 40 wordCount -= 1 41 wordToCount[startWord, default: 1] -= 1 42 startIndex += wordLength 43 } 44 45 if wordCount == words.count { 46 startingIndices.append(startIndex) 47 48 let startWord = String(string[startIndex..<(startIndex+wordLength)]) 49 wordCount -= 1 50 wordToCount[startWord, default: 1] -= 1 51 startIndex += wordLength 52 } 53 54 } else { 55 // reset 56 startIndex = j+wordLength 57 wordToCount = [:] 58 wordCount = 0 59 } 60 } 61 } 62 63 return startingIndices 64 } 65 } 424ms 1 class Solution { 2 func findSubstring(_ s: String, _ words: [String]) -> [Int] { 3 4 guard !words.isEmpty else { 5 return [] 6 } 7 guard !s.isEmpty else { 8 return words.contains(s) ? [0] : [] 9 } 10 11 let string = Array(s) 12 let wordLength = words[0].count 13 let totalWordLength = wordLength * words.count 14 15 guard totalWordLength <= string.count else { 16 return [] 17 } 18 19 let originalWordToCount = words.reduce(into: [:], { $0[$1, default: 0] += 1 }) 20 21 var startingIndices: [Int] = [] 22 23 for i in 0..<wordLength { 24 25 var startIndex = i 26 var currentWordToCount = originalWordToCount 27 28 for j in stride(from: i, to: string.count-wordLength+1, by: wordLength) { 29 30 let word = String(string[j..<(j+wordLength)]) 31 32 if let originalCount = originalWordToCount[word] { 33 34 while currentWordToCount[word] == nil { 35 let startWord = String(string[startIndex..<(startIndex+wordLength)]) 36 startIndex += wordLength 37 currentWordToCount[startWord, default: 0] += 1 38 } 39 40 if let currentCount = currentWordToCount[word] { 41 if currentCount == 1 { 42 currentWordToCount[word] = nil 43 } else { 44 currentWordToCount[word] = currentCount-1 45 } 46 } 47 48 if currentWordToCount.isEmpty { 49 startingIndices.append(startIndex) 50 51 // get a new combination 52 let startWord = String(string[startIndex..<(startIndex+wordLength)]) 53 startIndex += wordLength 54 currentWordToCount[startWord] = 1 55 } 56 57 } else { 58 // reset 59 startIndex = j+wordLength 60 currentWordToCount = originalWordToCount 61 } 62 } 63 } 64 65 return startingIndices 66 } 67 } 1128ms 1 class Solution { 2 func findSubstring(_ s: String, _ words: [String]) -> [Int] { 3 if words.isEmpty { 4 return [] 5 } 6 let wordLen = words[0].count 7 let substrLen = words.count * wordLen 8 9 if s.count < substrLen { 10 return [] 11 } 12 13 var answer = [Int]() 14 answer.reserveCapacity(s.count) 15 16 var dict = [String:Int]() 17 for w in words { 18 var count = 1 19 if let v = dict[w] { 20 count = count + v 21 } 22 dict[w] = count 23 } 24 25 var i = s.startIndex 26 let end = s.index(s.endIndex, offsetBy: -substrLen) 27 while i <= end { 28 if isSubstring(s[i..<s.index(i, offsetBy:substrLen)], dict, wordLen) { 29 answer.append(s.distance(from: s.startIndex, to: i)) 30 } 31 i = s.index(after: i) 32 } 33 return answer 34 } 35 36 func isSubstring(_ s: Substring, _ words: [String:Int], _ wordLen: Int) -> Bool { 37 var d = words 38 var substr = s 39 while !substr.isEmpty { 40 let w = String(substr[substr.startIndex..<substr.index(substr.startIndex, offsetBy: wordLen)]) 41 if let c = d[w], c > 0 { 42 d[w] = c - 1 43 } else { 44 return false 45 } 46 substr = substr[substr.index(substr.startIndex, offsetBy: wordLen)...] 47 } 48 return true 49 } 50 } 1852ms 1 class Solution { 2 func findSubstring(_ s: String, _ words: [String]) -> [Int] { 3 if s == nil || words.count == 0 { 4 return [] 5 } 6 var result: [Int] = [] 7 var dict1: [String: Int] = [String: Int]() 8 var dict2: [String: Int] = [String: Int]() 9 let stringLength: Int = s.count 10 let wordsListSize: Int = words.count 11 let wordLength: Int = words[0].count 12 for i in 0 ..< wordsListSize { 13 if dict1[words[i]] == nil { 14 dict1[words[i]] = 1 15 } else { 16 dict1[words[i]]! += 1 17 } 18 } 19 var s1: String 20 var s2: String 21 var counter1: Int 22 var counter2: Int 23 for i in 0 ..< wordLength { 24 counter1 = 0 25 counter2 = i 26 var j = i; 27 while j < stringLength { 28 s1 = s[j..<j+wordLength] 29 if dict1[s1] == nil { 30 dict2.removeAll(keepingCapacity: false) 31 counter1 = 0 32 counter2 = j + wordLength 33 } else if dict2[s1] == nil || dict2[s1]! < dict1[s1]! { 34 if dict2[s1] == nil { 35 dict2[s1] = 1 36 } else { 37 dict2[s1]! += 1 38 } 39 counter1 += 1 40 } else { 41 s2 = s[counter2..<counter2+wordLength] 42 while s2 != s1 { 43 dict2[s2]! -= 1 44 counter1 -= 1 45 counter2 += wordLength 46 s2 = s[counter2..<counter2+wordLength] 47 } 48 counter2 += wordLength 49 } 50 if counter1 == wordsListSize { 51 result.append(counter2) 52 s2 = s[counter2..<counter2+wordLength] 53 dict2[s2]! -= 1 54 counter1 -= 1 55 counter2 += wordLength 56 } 57 j += wordLength 58 } 59 dict2.removeAll(keepingCapacity: false) 60 } 61 return result 62 } 63 } 64 65 private extension String { 66 subscript (range: Range<Int>) -> String { 67 guard let localEndIndex = self.index(self.startIndex, offsetBy: range.upperBound, limitedBy: self.endIndex) else { 68 return String(self[self.index(self.startIndex, offsetBy: range.lowerBound)..<self.endIndex]) 69 } 70 return String(self[self.index(self.startIndex, offsetBy: range.lowerBound)..<localEndIndex]) 71 } 72 } 3192ms 1 class Solution { 2 func findSubstring(_ s: String, _ words: [String]) -> [Int] { 3 if words.count == 0 { return [] } 4 let len = words[0].count 5 6 let s = Array(s.characters) 7 let concatLen = len * words.count 8 9 if s.count < concatLen { return [] } 10 11 // Map word to count 12 var dict = [String: Int]() 13 for i in 0..<words.count { 14 let count = (dict[words[i]] ?? 0) + 1 15 dict[words[i]] = count 16 } 17 18 var res = [Int]() 19 for i in 0..<(s.count-words.count*len+1) { 20 var track = [String: Int]() 21 var ok = true 22 let startSequence = (0..<words.count).map { i + $0 * len } 23 for start in startSequence { 24 let substring = String(s[start..<start+len]) 25 let count = (track[substring] ?? 0) + 1 26 if count > (dict[substring] ?? 0) { 27 ok = false 28 break 29 } 30 track[substring] = count 31 } 32 33 if ok { 34 res.append(i) 35 } 36 } 37 38 return res 39 } 40 } 3480ms 1 class Solution { 2 func findSubstring(_ s: String, _ words: [String]) -> [Int] { 3 guard s.count > 0 && words.count > 0 else { 4 return [] 5 } 6 7 var counts = [String: Int]() 8 words.forEach { word in 9 counts[word, default: 0] += 1 10 } 11 12 var indices = [Int]() 13 let ss = s.utf8CString 14 let n = s.count 15 let wc = words.count 16 let len = words.first!.count 17 for i in 0..<(n - wc * len + 1) { 18 var seen = [String: Int]() 19 var j = 0 20 while j < wc { 21 let cs = Array(ss[(i + j * len)..<(i + (j + 1) * len)]) + [0] 22 let word = String(cString: cs) 23 if words.contains(word) { 24 seen[word, default: 0] += 1 25 if seen[word]! > counts[word]! { 26 break 27 } 28 } else { 29 break 30 } 31 j += 1 32 } 33 34 if j == wc { 35 indices.append(i) 36 } 37 } 38 return indices 39 } 40 } 3556ms 1 class Solution { 2 func findSubstring(_ s: String, _ words: [String]) -> [Int] { 3 var results:[Int] = [] 4 if s == nil || s.isEmpty || words == nil || words.isEmpty {return results} 5 var h:[String: Int] = [String: Int]() |
请发表评论