LeetCode 820: Short Encoding of Words Solution

Master LeetCode problem 820 (Short Encoding of Words), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

820. Short Encoding of Words

Medium

Array Hash Table String Trie

Problem Explanation

Explanation

To find the length of the shortest reference string that encodes an array of words, we need to build the string by appending each word followed by a '#' character. We then check if any existing word is a suffix of another word in the list. If a word is a suffix of another word, we skip encoding it. Finally, we return the length of the resulting reference string.

Create a set to store all words.
Iterate over each word and add it to the set.
For each word, iterate over all suffixes of the word and remove them from the set.
Calculate the total length of the set of unique words plus the length of the set.

Solution Code

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int minimumLengthEncoding(String[] words) {
        Set<String> set = new HashSet<>();
        for (String word : words) {
            set.add(word);
        }
        
        for (String word : words) {
            for (int i = 1; i < word.length(); i++) {
                set.remove(word.substring(i));
            }
        }
        
        int length = 0;
        for (String word : set) {
            length += word.length() + 1;
        }
        
        return length;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 820 (Short Encoding of Words)?

This page provides optimized solutions for LeetCode problem 820 (Short Encoding of Words) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 820 (Short Encoding of Words)?

The time complexity for LeetCode 820 (Short Encoding of Words) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 820 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 820 in Java, C++, or Python.

Back to LeetCode Solutions