The idea is to remove every suffix of words[i] where i = (0, word.length -1)
/**
* @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)
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)