820

820. Short Encoding of Words (Medium)

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.

Solution 1.

// OJ: https://leetcode.com/problems/short-encoding-of-words/
// Author: github.com/lzl124631x
// Time: O(NlogN * W)
// Space: O(W)
class Solution {
public:
    int minimumLengthEncoding(vector<string>& A) {
        string prev = "";
        int ans = 0;
        for (auto &s : A) reverse(begin(s), end(s));
        sort(begin(A), end(A));
        for (auto &s : A) {
            if (prev != "" && (s.size() < prev.size() || s.substr(0, prev.size()) != prev)) { // the current string can't cover the previous string, must start a new segment.
                ans += 1 + prev.size(); // close the previous segment.
            }
            prev = s;
        }
        return ans + 1 + prev.size();
    }
};

Solution 2. Trie

// OJ: https://leetcode.com/problems/short-encoding-of-words/
// Author: github.com/lzl124631x
// Time: O(NW)
// Space: O(NW)
struct TrieNode {
    TrieNode *next[26] = {};
    bool isLeaf = true;
};
class Solution {
    int dfs(TrieNode *root, int len = 0) {
        if (!root) return 0;
        if (root->isLeaf) return len + 1;
        int ans = 0;
        for (int i = 0; i < 26; ++i) {
            if (root->next[i]) ans += dfs(root->next[i], len + 1);
        }
        return ans;
    }
public:
    int minimumLengthEncoding(vector<string>& A) {
        TrieNode root;
        for (auto &s : A) {
            auto node = &root;
            reverse(begin(s), end(s));
            for (char c : s) {
                if (!node->next[c - 'a']) node->next[c - 'a'] = new TrieNode();
                node->isLeaf = false;
                node = node->next[c - 'a'];
            }
        }
        return dfs(&root);
    }
};