[LeetCode] Short Encoding of Words

Problem: 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:

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#"

Input: words = ["t"]
Output: 2
Explanation: A valid encoding would be s = "t#" and indices = [0].

Approach: The intuition here is that if a string is a suffix of another string then we don't have to add suffix string in the result as it is already covered. Just look at the implementation to understand how to use this fact.

Implementation in C#:

    public int MinimumLengthEncoding(string[] words) 

    {

        HashSet<string> wordSet = new HashSet<string>(words);

        foreach (string word in words)

        {

            if (!wordSet.Contains(word))

            {

                continue;

            }

            for (int i = 1; i < word.Length; ++i)

            {

                wordSet.Remove(word.Substring(i));

            }

        }

        int length = 0;

        foreach (string word in wordSet)

        {

            length += word.Length + 1;

        }

        return length;      

    }

Complexity: O(n^2) where n is the total number of characters in the input array words.