Skip to content

Instantly share code, notes, and snippets.

@jzallas
Created March 6, 2021 04:49
Show Gist options
  • Save jzallas/d3a31ccb814e52e2bf8d28fda000e33f to your computer and use it in GitHub Desktop.
Save jzallas/d3a31ccb814e52e2bf8d28fda000e33f to your computer and use it in GitHub Desktop.
Basic Trie in kotlin
// because this keeps coming up in coding challenges and I hate solving this from scratch
class Node(
var word: String? = null,
val next: MutableList<Node?> = MutableList(26) { null }
)
// inserting
fun Node.insert(word: String) {
var current = this
word.forEach {
val index = it - 'a'
current = current.next[index]
?: Node().apply { current.next[index] = this }
}
current.word = word
}
// constructing
val root = Node()
myList.forEach { root.insert(it) }
// lookup char
fun Node.get(char: Char) =
this.next[char - 'a']
// lookup word
fun Node.find(word: String): Boolean {
var current = this
word.forEach {
current = current.get(it) ?: return false
}
return current.word == word
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment