leetcode: 820. Short Encoding of Words

problem

• https://leetcode.com/problems/short-encoding-of-words/

Set

• O(N * K^2) time
• N is number of word
• K is length of word

class Solution {

    fun minimumLengthEncoding(words: Array<String>): Int {
        val set = mutableSetOf<String>()  
        words.forEach { word ->
            set.add(word)
        }
        
        words.forEach { word ->
            val len = word.length
            // remove all prefix of word except whole word
            for (i in 1 until len) {
                set.remove(word.substring(i))            
            }            
        }
        
        var answer = 0
        set.forEach { word ->
            answer += (word.length + 1) // include '#''
        }
        return answer
    }
}

trie with isEnd Boolean variable

• O(N * K) time

data class Node(val table: MutableMap<Char, Node>, var isEnd: Boolean)

class Solution {
    var answer = 0
    
    fun minimumLengthEncoding(words: Array<String>): Int {
    	// The isEnd value cannot be calculated properly if the shorter word with the same prefix is calculated later.
	    words.sortBy { it.length }
        
        val root = Node(mutableMapOf(), false)    
        
        words.forEach { word ->
            val len = word.length
            var curr = root
            for (i in len - 1 downTo(0)) {
                if (curr.isEnd) curr.isEnd = false
                if (curr.table[word[i]] == null) {
                    val child = Node(mutableMapOf(), false)
                    curr.table[word[i]] = child
                }
                curr = curr.table[word[i]]!!
            }
            curr.isEnd = true            
        }
        root.table.forEach { key, value ->
            dfs(value, 1)
        }
        return answer
    }
    
    fun dfs(node: Node, length: Int) {
        if (node.isEnd) {
            answer += (length + 1) // include '#'
            return
        }
        
        node.table.forEach { key, value ->
            dfs(value, length + 1)
        }
    }
}

trie with leaf nodes

data class Node(val table: MutableMap<Char, Node>, val depth: Int)

class Solution {

    fun minimumLengthEncoding(words: Array<String>): Int {
        // remove duplicated word
        val noDupWords = words.distinct()
        val root = Node(mutableMapOf(), 0)
        // leaf nodes
        val leaves = mutableListOf<Node>()
        
        noDupWords.forEach { word ->
            var curr = root
            val len = word.length
            for (i in len - 1 downTo(0)) {
                if (curr.table[word[i]] == null) {
                    val child = Node(mutableMapOf(), curr.depth + 1)
                    curr.table[word[i]] = child
                }
                curr = curr.table[word[i]]!!
            }
            leaves.add(curr)
        }
        
        var answer = 0
        leaves.forEach { leaf ->
            if (leaf.table.isEmpty()) answer += (leaf.depth + 1) // include '#'
        }
        return answer
    }
}