Skip to content

Instantly share code, notes, and snippets.

@not-for-me
Created January 20, 2019 14:16
Show Gist options
  • Save not-for-me/f7853dcf2641ccd5a7316d23ece1cdb7 to your computer and use it in GitHub Desktop.
Save not-for-me/f7853dcf2641ccd5a7316d23ece1cdb7 to your computer and use it in GitHub Desktop.
Hacker Rank: No Prefix Set
import java.util.*
// https://www.hackerrank.com/challenges/no-prefix-set/problem
data class TrieNode(
val c: Char = '-',
var cnt: Int = 0,
var isLeaf: Boolean = false,
val children: MutableMap<Char, TrieNode> = HashMap()
)
fun insert(root: TrieNode, keyword: String): Boolean {
var cur: TrieNode = root
var idx = 0
for (c in keyword) {
val child = cur.children.getOrDefault(c, TrieNode(c = c))
child.cnt++
if (child.isLeaf) {
return false
}
if (keyword.length - 1 == idx && child.children.isNotEmpty()) {
return false
}
cur.children[c] = child
cur = child
idx++
}
cur.isLeaf = true
return true
}
fun main(args: Array<String>) {
val scanner = Scanner(System.`in`)
val testCnt = scanner.nextLine().toInt()
val root = TrieNode()
var prefix = ""
for (i in 0 until testCnt) {
val keyword = scanner.nextLine()
if (!insert(root, keyword)) {
prefix = keyword
break
}
}
val result = if (prefix.isNotEmpty()) "BAD" else "GOOD"
println("$result SET")
if (prefix.isNotEmpty()) {
println(prefix)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment