820. Short Encoding of Words

Time: O(Σ len)

Space: O(Σ len)

Intuition

Build a trie of reversed words. A word needs its own entry only if it's not a suffix of another word. Count total characters for words that are trie leaves.

Algorithm

1Build suffix trie (insert reversed words).
2Leaves of the trie are words not suffixed by others.
3Sum up length+1 for each leaf.
4Alternative: put all words in a set; for each word's suffix, if it's also in set, remove it.

Common Pitfalls

•Two words sharing a suffix share a trie path. Only leaves contribute to the encoded length.

820.cs

// Approach: Insert reversed words into a Trie; each leaf node (unique suffix) contributes word length + 1 to the encoded string.
// Time: O(Σ len) Space: O(Σ len)

public class Solution
{
    public int MinimumLengthEncoding(string[] words)
    {
        int ans = 0;
        var root = new TrieNode();
        var heads = new List<TrieNode>();

        foreach (string word in new HashSet<string>(words))
            heads.Add(insert(root, word));

        foreach (TrieNode head in heads)
        {
            if (head.children.All(child => child == null))
                ans += head.depth + 1;
        }

        return ans;
    }

    private TrieNode insert(TrieNode root, string word)
    {
        TrieNode node = root;
        char[] reversedWord = word.ToCharArray();
        Array.Reverse(reversedWord);
        foreach (char ch in reversedWord)
        {
            int ind = ch - 'a';
            if (node.children[ind] == null)
                node.children[ind] = new TrieNode();
            node = node.children[ind];
        }
        node.depth = word.Length;
        return node;
    }
}

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

Was this solution helpful?