Algorithm
Problem Name: 820. Short Encoding of Words
A valid encoding of an array of words is any reference string s and array of indices indices such that:
words.length == indices.length- The reference string
sends with the'#'character. - For each index
indices[i], the substring ofsstarting fromindices[i]and up to (but not including) the next'#'character is equal towords[i].
Given an array of words, return the length of the shortest reference string s possible of any valid encoding of words.
Example 1:
Input: words = ["time", "me", "bell"]
Output: 10
Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5]. words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#" words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#" words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"
Example 2:
Input: words = ["t"] Output: 2 Explanation: A valid encoding would be s = "t#" and indices = [0].
Constraints:
1 <= words.length <= 20001 <= words[i].length <= 7words[i]consists of only lowercase letters.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
private:
struct TrieNode{
int length;
bool isWord;
vector < TrieNode*>next;
TrieNode(int x): length(x), isWord(false), next(vector<TrieNode*>(26)){}
};
TrieNode* root;
public:
int minimumLengthEncoding(vector < string>& words) {
root = new TrieNode(0);
int count = 0;
for(auto& s: words){
reverse(s.begin(), s.end());
buildTrie(s, count);
}
return count;
}
void buildTrie(string& s, int& count){
auto p = root;
bool newWord = false;
for(int i = 0; i < s.size(); i++){
char c = s[i];
if(!p->next[c - 'a']){
if(!newWord){
count++;
if(p->isWord){
count--;
count -= p->length;
p->isWord = false;
}
newWord = true;
}
p->next[c - 'a'] = new TrieNode(i + 1);
}
p = p->next[c - 'a'];
}
if(newWord){
count += p->length;
p->isWord = true;
}
}
};
Input
words = ["time", "me", "bell"]
Output
10
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int minimumLengthEncoding(String[] words) {
TrieNode root = new TrieNode();
Map < TrieNode, Integer> nodes = new HashMap<>();
for (int i = 0; i < words.length; i++) {
TrieNode curr = root;
for (int j = words[i].length() - 1; j >= 0; j--) {
if (curr.children[words[i].charAt(j) - 'a'] == null) {
curr.children[words[i].charAt(j) - 'a'] = new TrieNode();
curr.count++;
}
curr = curr.children[words[i].charAt(j) - 'a'];
}
nodes.put(curr, i);
}
int result = 0;
for (TrieNode node : nodes.keySet()) {
if (node.count == 0) {
result += words[nodes.get(node)].length() + 1;
}
}
return result;
}
private class TrieNode {
TrieNode[] children;
int count;
public TrieNode() {
this.children = new TrieNode[26];
this.count = 0;
}
}
}
Input
words = ["time", "me", "bell"]
Output
10
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def minimumLengthEncoding(self, words):
"""
:type words: List[str]
:rtype: int
"""
s = set(words)
for word in words:
for i in range(1, len(word)): s.discard(word[i:])
return sum(len(w) + 1 for w in s)
Input
words = ["t"]
Output
2