/
PrefixTree.kt
111 lines (92 loc) · 2.73 KB
/
PrefixTree.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
102
103
104
105
106
107
108
109
@file:JvmName("Utils")
package de.halirutan.wlinfo
import java.lang.RuntimeException
import java.lang.StringBuilder
fun createReducedRegex(words: Array<String>): String {
return createReducedRegex(words.toList())
}
fun createReducedRegex(words: List<String>): String {
val trie = Trie(words)
val builder = StringBuilder()
fun visit(node: Node) {
builder.append(
if (node.content == '$') {
"\\\\$"
} else {
node.content
}
)
if (node.hasChildren()) {
val keys = node.children.keys.sorted()
if (keys.size == 1) {
if (node.isWord) {
builder.append("(?:")
visit(node.children[keys[0]]!!)
builder.append(")?")
} else {
visit(node.children[keys[0]]!!)
}
} else {
builder.append("(?:")
keys.forEachIndexed { id, c ->
visit(node.children[c]!!)
if (id < keys.size - 1) {
builder.append("|")
}
}
builder.append(")")
if (node.isWord) {
builder.append("?")
}
}
}
}
visit(trie.root)
return builder.toString().trim()
}
private class Trie() {
val root: Node = Node(' ')
constructor(words: List<String>) : this() {
words.forEach(::insert)
}
private fun insert(word: String) {
if (contains(word) || !isValidKey(word)) return
var current = root
word.forEach { char ->
current = current.getOrCreateChild(char)
}
current.isWord = true
}
fun contains(word: String): Boolean {
var current = root
word.forEach { char ->
if (current.hasChild(char)) {
current = current.children[char] ?: throw RuntimeException("Key $char not a child")
} else {
return false
}
}
return current.isWord
}
private fun isValidKey(word: String): Boolean {
return word.isNotBlank()
}
}
private class Node(val content: Char) {
val children: MutableMap<Char, Node> = hashMapOf()
var isWord = false
fun hasChild(char: Char): Boolean {
return children.containsKey(char)
}
fun hasChildren(): Boolean {
return !children.isNullOrEmpty()
}
fun getOrCreateChild(char: Char): Node {
return if (children.containsKey(char)) {
children[char]!!
} else {
children[char] = Node(char)
children[char]!!
}
}
}