-
Notifications
You must be signed in to change notification settings - Fork 0
/
MapSum.kt
101 lines (89 loc) · 2.82 KB
/
MapSum.kt
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
package problems
import java.util.HashMap
class MapSumTrie {
companion object {
private const val ALPHABET_SIZE = 26
}
class TrieNode(var count: Int) {
val treeList = Array<TrieNode?>(ALPHABET_SIZE){ null }
}
//Used Array because cannot set value with List
private val root = TrieNode(0)
private val keyMap = HashMap<String, Int>()
fun insert(key: String, value: Int) {
var node = root
if (keyMap.contains(key)) {
for (i in 0 until key.length) {
//duplicated node initialization
val index = key[i] - 'a'
node.treeList[index]?.let {
if (it.count != 0) {
it.count = it.count - (keyMap[key] ?: 0) + value
}
node = it
}
}
} else {
for (i in 0 until key.length) {
//duplicated node initialization
val index = key[i] - 'a'
node.treeList[index]?.let {
if (it.count != 0) {
it.count += value
}
node = it
} ?: run {
val newNode = TrieNode(0)
node.treeList[index] = newNode
node = newNode
}
}
}
keyMap[key] = value
node.count = value
}
fun search(str: String): Int {
var node = root
var count = 0
for (i in 0 until str.length) {
val index = str[i] - 'a'
node.treeList[index]?.let {
count += it.count
node = it
} ?: return 0
}
return count
}
}
class MapSum {
private val prefixMap = HashMap<String, Int>()
private val keyMap = HashMap<String, Int>()
fun insert(key: String, value: Int) {
val sb = StringBuilder()
if (keyMap.contains(key)) {
//- and +
for (i in 0 until key.length) {
sb.append(key[i])
if (prefixMap.containsKey(sb.toString())) {
prefixMap[sb.toString()] = (prefixMap[sb.toString()] ?: 0) - (keyMap[key] ?: 0) + value
} else {
prefixMap[sb.toString()] = value
}
}
} else {
//only +
for (i in 0 until key.length) {
sb.append(key[i])
if (prefixMap.containsKey(sb.toString())) {
prefixMap[sb.toString()] = (prefixMap[sb.toString()] ?: 0) + value
} else {
prefixMap[sb.toString()] = value
}
}
}
keyMap[key] = value
}
fun sum(prefix: String): Int {
return prefixMap[prefix] ?: 0
}
}