## Sunday, May 13, 2018

### LeetCode 820 - Short Encoding of Words

https://leetcode.com/problems/short-encoding-of-words/description/
Given a list of words, we may encode it by writing a reference string S and a list of indexes A.
For example, if the list of words is ["time", "me", "bell"], we can write it as S = "time#bell#" and indexes = [0, 2, 5].
Then for each index, we will recover the word by reading from the reference string from that index until we reach a "#" character.
What is the length of the shortest reference string S possible that encodes the given words?
Example:
Input: words = ["time", "me", "bell"]
Output: 10
Explanation: S = "time#bell#" and indexes = [0, 2, 5].

Note:
1. 1 <= words.length <= 2000.
2. 1 <= words[i].length <= 7.
3. Each word has only lowercase letters.
https://leetcode.com/problems/short-encoding-of-words/discuss/125784/Trie-Solution
As in Approach #1, the goal is to remove words that are suffixes of another word in the list.
Algorithm
To find whether different words have the same suffix, let's put them backwards into a trie (prefix tree). For example, if we have "time" and "me", we will put "emit" and "em" into our trie.
After, the leaves of this trie (nodes with no children) represent words that have no suffix, and we will count sum(word.length + 1 for word in words).
• Time Complexity: $O(\sum w_i)$, where $w_i$ is the length of words[i].
• Space Complexity: $O(\sum w_i)$, the space used by the trie.

public int minimumLengthEncoding(String[] words) {
TrieNode trie = new TrieNode();
Map<TrieNode, Integer> nodes = new HashMap();

for (int i = 0; i < words.length; ++i) {
String word = words[i];
TrieNode cur = trie;
for (int j = word.length() - 1; j >= 0; --j)
cur = cur.get(word.charAt(j));
nodes.put(cur, i);
}

int ans = 0;
for (TrieNode node: nodes.keySet()) {
if (node.count == 0)
ans += words[nodes.get(node)].length() + 1;
}
return ans;

}
}

class TrieNode {
TrieNode[] children;
int count;
TrieNode() {
children = new TrieNode[26];
count = 0;
}
public TrieNode get(char c) {
if (children[c-'a'] == null) {
children[c-'a'] = new TrieNode();
count++;
}
return children[c - 'a'];
}
public int minimumLengthEncoding(String[] words) {
Trie trie = new Trie();
for (String word : words) {
trie.insert(new StringBuilder(word).reverse().toString());
}

return trie.getLongestWords().stream().map(str -> str.length() + 1).mapToInt(i -> (int) i).sum();
}

private static class TrieNode {
public TrieNode[] children = new TrieNode[26];
public boolean isEnd;
public boolean hasChild;

@Override
public String toString() {
return "TrieNode [children=" + Arrays.toString(children) + ", isEnd=" + isEnd + "]";
}
}

private static class Trie {
public TrieNode root = new TrieNode();
// em, emtia, will only contains emtia
private Set<String> longestWords = new HashSet<>();

public void insert(String word) {
TrieNode curr = root;
StringBuilder currWord = new StringBuilder();
for (char ch : word.toCharArray()) {
int index = ch - 'a';
TrieNode child = curr.children[index];
curr.hasChild = true;
if (child == null) {
child = new TrieNode();
curr.children[index] = child;
}
currWord.append(ch);
if (child.isEnd) {
longestWords.remove(currWord.toString());
// so we don't remove again, but it doesn't matter
// child.isEnd= false;
}
curr = child;

}
curr.isEnd = true;
// Different case: em, emit, or emit, em
if (!curr.hasChild) { // don't forget this BUG
}
}

public Set<String> getLongestWords() {
return longestWords;
}

@Override
public String toString() {
return "Trie [root=" + root + ", longestWords=" + longestWords + "]";
}

}
https://leetcode.com/problems/short-encoding-of-words/discuss/125869/Simple-Concept-using-Trie
Firstly, sort the Strings based on their length in the descending order.
For each word in the String insert the word in Trie from right to left. For "time" insert "emit" in Trie.
Notice, that for all the string that are suffixes of another string, you won't need to create a new TrieNode.
Keep track of whether a new node was created when inserting into the trie. If yes, then add this word into the reference String S else continue.
Ex:
words = ["time", "me", "bell"]
Sort in descending order of length
words = ["time", "bell", "me"]
Let ans = 0
Inserting "time" in the Trie, we insert "emit" and create 4 TrieNodes starting from the root. (ans = 4(length of "time")+1(1 for the #))
Similarly, while inserting "bell" we will create new TrieNodes (ans+= 4 + 1)
However, while inserting "me" we already have an edges from root labelled as "e" and a node from "e" labelled as "m" and hence no new trie node is created.
Hence we get ans=10.
    class TrieNode {
TrieNode[] child = new TrieNode[26];
}

public boolean adder(String word, TrieNode root){
boolean newNeed = false;
for(int i = word.length() -1; i>=0; --i){
char c = word.charAt(i);
if(root.child[c-'a']==null){
newNeed = true;
root.child[c-'a'] = new TrieNode();
}
root = root.child[c-'a'];
}
return newNeed;
}

public int minimumLengthEncoding(String[] words) {
if(words == null || words.length < 1)return 0;
Arrays.sort(words, (a, b)->b.length() - a.length());
TrieNode root = new TrieNode();
int len = 0 ;
for(String word : words){
len+=word.length()+1;
}
}
return len;
}


X. Store Prefixes
https://leetcode.com/problems/short-encoding-of-words/discuss/125811/C++JavaPython-Easy-Understood-Solution-with-Explanation
Base on @awice's idea. This solution is not my intuition but it is really simple to write, compared with Trie solution.
1. Build a set of words.
2. Iterate on all words and remove all suffixes of every word from the set.
3. Finally the set will the set of all encoding words.
4. Iterate on the set and return sum(word's length + 1 for every word in the set)
Complexity
O(NK^2) for time and 'O(NK)' for space.
It is really kind of K with K <= 7, almost ignorable.
I should have suggested for bigger 'K' cases.
I believe it will take more time for most people to solve this problem if we have a big K.

If a word X is a suffix of Y, then it does not need to be considered, as the encoding of Y in the reference string will also encode X. For example, if "me" and "time" is in words, we can throw out "me" without changing the answer.
If a word Y does not have any other word X (in the list of words) that is a suffix of Y, then Y must be part of the reference string.
Thus, the goal is to remove words from the list such that no word is a suffix of another. The final answer would be sum(word.length + 1 for word in words).
Algorithm
Since a word only has up to 7 suffixes (as words[i].length <= 7), let's iterate over all of them. For each suffix, we'll try to remove it from our words list. For efficiency, we'll make words a set.
• Time Complexity: $O(\sum w_i^2)$, where $w_i$ is the length of words[i].
• Space Complexity: $O(\sum w_i)$, the space used in storing suffixes.