LeetCode 820: Short Encoding of Words

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.

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

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;
    }
}