Skip to content

Instantly share code, notes, and snippets.

@dicarlomagnus
Created December 30, 2019 01:31
Show Gist options
  • Save dicarlomagnus/850f051a8ad5c6ef1c99f10299f0a0cf to your computer and use it in GitHub Desktop.
Save dicarlomagnus/850f051a8ad5c6ef1c99f10299f0a0cf to your computer and use it in GitHub Desktop.
Trie in kotlin, Insert, find and fetch
fun main() {
var trie = Trie()
Trie.insert(trie, "hello", "hi", "hey", ""," *") //Inserting "hello", "hi", "hey" into the trie, "*" will be replace by empty string
println(Trie.find(trie, "hey")) //checking out if "hey exists inside the trie"
println(Trie.fetch(trie)) // traversing the trie and get all the words inside of it and printing them
}
class Trie(var node: MutableMap<Char, Trie> = mutableMapOf()){
companion object {
fun insert(trie: Trie, vararg words: String) {
words.map{
it.replace("*","")}
.filter { it.isNotEmpty()}
.forEach {
_insert(trie, it)
}
}
private fun _insert(trie: Trie, word: String) {
if (word.isEmpty()) {
trie.node['*'] = Trie()
return
}
val c = word[0]
if (!trie.node.contains(c)) {
trie.node[c] = Trie()
}
_insert(trie.node[c]!!, word.substring(1))
}
fun find(trie: Trie, word: String): Boolean {
if (word.isEmpty()) {
return true
}
val c = word[0]
if (!trie.node.containsKey(c)) {
return false
}
return find(trie.node[c]!!, word.substring(1))
}
fun fetch(trie: Trie): MutableList<String> {
val list = mutableListOf<String>()
trie.node.forEach { entry ->
if (entry.key == '*') {
list.add("")
} else {
fetch(entry.value).forEach { s ->
val string = entry.key + s
list.add(string)
}
}
}
return list
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment