[leetcode] Short Encoding of Words

problem

code

The idea is to remove every suffix of words[i] where i = (0, word.length -1)

1st try: brute force

/**
 * @param {string[]} words
 * @return {number}
 */
var minimumLengthEncoding = function(words) {
    const len = words.length;
    if (len <= 1) return words[0].length + 1;
    
    words.sort((a, b) => b.length - a.length);
    // console.log(words);
    
    for (let i = 0; i < len; i++) {
        const temp = words[i];
        if (temp == undefined)
            continue;
        for (let j = i + 1; j < len; j++) {
            if(temp.endsWith(words[j]))
                words[j] = undefined;
        }
    }
    
    let count = 0;    
    for (let i = 0; i < len; i++) {
        if (words[i] != undefined)
            count += words[i].length + 1;
    }
    
    return count;
};

// O(Math.min(s1.length, s2.length) => 7)
const endsWith = (s1, s2) => {
    for (
      let i = s1.length - 1, j = s2.length - 1; 
      	i >= 0, j >= 0; 
      		i--, j--) {
      if (s1.charAt(i) != s2.charAt(j)) 
        return false;
    }
    return true;
}

Time: O(NlogN + N^2*M) = O(MN^2), N is the length of the words, M is the length of words[i]
Space: O(1)

2nd try: with Trie

var minimumLengthEncoding = function(words) {
        const trie = new TrieNode(); // root
		// (key, value) => (the last leaf of TrieNode, i of words[i])
  		const nodes = new Map(); 
		
        for (let i = 0; i < words.length; ++i) {
            const word = words[i];
            let cur = trie;
            for (let j = word.length - 1; j >= 0; --j)
                cur = cur.getChild(word.charAt(j));
            nodes.set(cur, i)
        }
        let ans = 0;
        for (const node of nodes.keys()) {
            if (!node.visited)
                ans += words[nodes.get(node)].length + 1;
        }
        return ans;

};

class TrieNode {
    children;
    visited;
    
    constructor() {
        this.children = []; // or new Array(26)
        this.visited = false;
    }
    
    getChild = c => {
        const idx = c.charCodeAt() - 'a'.charCodeAt();
      	// if there is no children[idx], assign new TrieNode
      	// set count++ => there is a words[i] that ends with this node
        if (this.children[idx] == undefined) {
            this.children[idx] = new TrieNode();
            this.visited = true;
        }
      	// return the child
        return this.children[idx];
    }
}

Time: O(MN), N: length of words, M: max length of words[i]
Space: O(26M*N)