Untitled

class Solution {
    fun removeSubfolders(folder: Array<String>): List<String> {
        val trie = Trie()
        folder.forEach { trie.insert(it) }
        return folder.filter { trie.search(it) }
    }
}

class Trie {

    val root = TrieNode()

    class TrieNode {
        val edges = mutableMapOf<Char, TrieNode>()
        var isTerminated = false
    }

    fun insert(word: String) {
        var iter = root
        word.forEach {
            if (!iter.edges.containsKey(it))
                iter.edges.put(it, TrieNode())
            iter = iter.edges[it]!!
        }
        iter.isTerminated = true
    }

    fun search(word: String): Boolean {
        var iter = root
        word.forEachIndexed { idx, it ->
            if (idx < word.length - 1 && iter.isTerminated)
                return false
            iter = iter.edges[it]!!
        }

        return iter.isTerminated
    }
}