-
Notifications
You must be signed in to change notification settings - Fork 0
/
0030_Substring_with_Concatenation_of_All_Words.swift
76 lines (65 loc) · 2.04 KB
/
0030_Substring_with_Concatenation_of_All_Words.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class Solution {
func hash(_ c: Character) -> Int {
Int(c.asciiValue!) * Int(c.asciiValue!)
}
func hash(_ s: [Character]) -> Int {
s.reduce(0) {
$0 + hash($1)
}
}
func findSubstring(_ s: String, _ words: [String]) -> [Int] {
if words.isEmpty {
return []
}
let s = Array(s)
let words = words.map({ Array($0) })
let len = words.first!.count
let wordsLen = words.count * len
if s.count < wordsLen { return [] }
let wordsHash = words.reduce(0, { $0 + hash($1) })
var good: Set<[Character]> = []
var bad: Set<[Character]> = []
var res: [Int] = []
var i = 0
var stringHash = 0
while i <= s.count - wordsLen {
if i == 0 {
stringHash = hash(Array(s[i..<i+wordsLen]))
} else {
stringHash += hash(s[i + wordsLen - 1]) - hash(s[i - 1])
}
if wordsHash == stringHash {
let subString = Array(s[i..<i + wordsLen])
if bad.contains(subString) {
i += 1
continue
}
if good.contains(subString) {
res.append(i)
i += 1
continue
}
var ok = true
var copy = words
for j in 0 ..< words.count {
let word = Array(s[(i + j * len) ..< (i + (j + 1) * len)])
if !copy.contains(word) {
ok = false
break
} else {
let index = copy.firstIndex(of: word)!
copy.remove(at: index)
}
}
if ok {
res.append(i)
good.insert(subString)
} else {
bad.insert(subString)
}
}
i += 1
}
return res
}
}