820. Short Encoding of Words LeetCode Solution

Last updated: February 20, 2025

In this guide, you will get 820. Short Encoding of Words LeetCode Solution with the best time and space complexity. The solution to Short Encoding of Words problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Short Encoding of Words solution in C++
Short Encoding of Words solution in Java
Short Encoding of Words solution in Python
Additional Resources

820. Short Encoding of Words LeetCode Solution image

Problem Statement of 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 s ends with the ‘#’ character.
For each index indices[i], the substring of s starting from indices[i] and up to (but not including) the next ‘#’ character is equal to words[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 <= 2000
1 <= words[i].length <= 7
words[i] consists of only lowercase letters.

Complexity Analysis

Time Complexity: O(\Sigma \texttt{words[i]})
Space Complexity: O(\Sigma \texttt{words[i]})

820. Short Encoding of Words LeetCode Solution in C++

struct TrieNode {
  vector<shared_ptr<TrieNode>> children;
  int depth = 0;
  TrieNode() : children(26) {}
};

class Solution {
 public:
  int minimumLengthEncoding(vector<string>& words) {
    int ans = 0;
    shared_ptr<TrieNode> root = make_shared<TrieNode>();
    vector<shared_ptr<TrieNode>> heads;

    for (const string& word : unordered_set<string>(words.begin(), words.end()))
      heads.push_back(insert(root, word));

    for (shared_ptr<TrieNode> head : heads)
      if (ranges::all_of(head->children,
                         [](const auto& child) { return child == nullptr; }))
        ans += head->depth + 1;

    return ans;
  }

 private:
  shared_ptr<TrieNode> insert(shared_ptr<TrieNode> root, const string& word) {
    shared_ptr<TrieNode> node = root;
    for (const char c : string{word.rbegin(), word.rend()}) {
      const int i = c - 'a';
      if (node->children[i] == nullptr)
        node->children[i] = make_shared<TrieNode>();
      node = node->children[i];
    }
    node->depth = word.length();
    return node;
  }
};
/* code provided by PROGIEZ */

820. Short Encoding of Words LeetCode Solution in Java

class TrieNode {
  public TrieNode[] children = new TrieNode[26];
  public int depth = 0;
}

class Solution {
  public int minimumLengthEncoding(String[] words) {
    int ans = 0;
    TrieNode root = new TrieNode();
    List<TrieNode> heads = new ArrayList<>();

    for (final String word : new HashSet<>(Arrays.asList(words)))
      heads.add(insert(root, word));

    for (TrieNode head : heads)
      if (Arrays.stream(head.children).allMatch(child -> child == null))
        ans += head.depth + 1;

    return ans;
  }

  private TrieNode insert(TrieNode root, final String word) {
    TrieNode node = root;
    for (final char c : new StringBuilder(word).reverse().toString().toCharArray()) {
      final int i = c - 'a';
      if (node.children[i] == null)
        node.children[i] = new TrieNode();
      node = node.children[i];
    }
    node.depth = word.length();
    return node;
  }
}
// code provided by PROGIEZ

820. Short Encoding of Words LeetCode Solution in Python

class TrieNode:
  def __init__(self):
    self.children: dict[str, TrieNode] = {}
    self.depth = 0


class Solution:
  def minimumLengthEncoding(self, words: list[str]) -> int:
    root = TrieNode()
    leaves = []

    def insert(word: str) -> TrieNode:
      node = root
      for c in reversed(word):
        node = node.children.setdefault(c, TrieNode())
      node.depth = len(word)
      return node

    for word in set(words):
      leaves.append(insert(word))

    return sum(leaf.depth + 1 for leaf in leaves
               if not len(leaf.children))
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents