Solution: Short Encoding of Words (ver. 2)
Tags: algorithms, javascript, java, python
Published: 2021-03-07 19:07:06

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/short-encoding-of-words/discuss/1095894).*

---

*__Note__: This is my second version of a solution for this problem. Due to the constraints listed for this problem, [the first version](https://dev.to/seanpgallivan/solution-short-encoding-of-words-39g0) is the more performant solution, but the nature of this problem really calls for a trie solution, so I've included a breakdown of the trie approach here, as well.*

---

#### [Leetcode Problem #820 (*Medium*): Short Encoding of Words](https://leetcode.com/problems/short-encoding-of-words/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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`.

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:|words = ["time", "me", "bell"]
Output:|10
Explanation:|A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].<br>words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#"<br>words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#"<br>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.

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

So a simple encoding of the input would be to add the '**#**' marker to the end of each word and then join them in a string. Per the instructions, this encoding can be made shorter if you can combine two or more words into one encoded word. In order to do this, the smaller word would have to be not just a substring of the larger word, but the *rightmost* substring, or its suffix.

A naive solution here would be to compare each word to each other word and examine if the larger word has the smaller word as its suffix, but with a range of up to **2000** words, that would mean almost **4 million** potential combinations.

But if we're asked to check for matching suffixes, we might also be thinking of a **trie** solution. A trie is a tree data structure in which you define branches of prefix (or in this case suffix) data. In this way, entries that share the same prefix will be grouped together and easy to identify.

When you build out a trie, you iterate through the granular segments of the data and go down existing branches of the trie when they exist and create them when they don't. For this problem, the entries are **words** and thus the granular segments are **characters**. We'll also be iterating through the characters in reverse order, since we're dealing with suffixes instead of prefixes.

![Trie Example](https://i.imgur.com/IwFkd6d.png)

We could fully build out the trie then later traverse the trie to calculate our answer (**ans**), but instead we can just keep our **ans** up-to-date as we build out the trie to be more efficient.

As we build out our trie, there are three things we have to look out for:
 - If any new branches are formed while processing a **word**, then that word must be new and we should add its length (plus 1 for the '#' at the end) to our **ans**.
 - If a **word** ends without forging a new branch, then it must be the suffix of an earlier word, so we shouldn't add its length to our **ans**.
 - If there are no other branches on the node in which the first new branch is formed while processing a **word**, then some earlier word must be a suffix to the current word, so we should subtract the already added amount from our **ans**.

The third check in particular will allow us to avoid needing to sort **W** before entry. In order to prevent the third check from triggering every time a word extends into new territory (which would happen with each new character), we can use a **boolean** flag (**newWord**) to mark only the first instance.

---

#### ***Implementation:***

Javascript and Python are a little more straightforward in their implementation of the trie. They can use a more simple **map** structure to good use.

For Java and C++, however, we'll want to use a **class** structure for our trie, but rather than use data structures with more overhead, we can improve efficiency by simplifying each node to an array of **26** elements, with each index corresponding to a **character**.

The one additional problem we face when converting from a map-type object to an ordered array is that we no longer have an easy way to tell whether or not the array is fully empty. To get around this, we can just add an **isEmpty** boolean flag to our **TrieNode** class.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var minimumLengthEncoding = function(W) {
    let len = W.length, trie = new Map(), ans = 1
    for (let word of W) {
        let curr = trie, newWord = false
        for (let j = word.length - 1; ~j; j--) {
            let char = word.charAt(j)
            if (!curr.size && !newWord)
                ans -= word.length - j
            if (!curr.has(char))
                newWord = true, curr.set(char, new Map())
            curr = curr.get(char)
        }
        if (newWord) ans += word.length + 1
    }
    return ans
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def minimumLengthEncoding(self, W: List[str]) -> int:
        trie, ans = defaultdict(), 1
        for word in W:
            curr, newWord = trie, False
            for i in range(len(word)-1,-1,-1):
                char = word[i]
                if not curr and not newWord: ans -= len(word) - i
                if char not in curr:
                    newWord = True
                    curr[char] = defaultdict()
                curr = curr[char]
            if newWord: ans += len(word) + 1
        return ans
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class TrieNode {
    TrieNode[] branch = new TrieNode[26];
    Boolean isEmpty = true;
}

class Solution {
    public int minimumLengthEncoding(String[] W) {
        TrieNode trie = new TrieNode();
        trie.branch = new TrieNode[26];
        int ans = 1;
        for (String word : W) {
            TrieNode curr = trie;
            Boolean newWord = false;
            for (int i = word.length() - 1; i >= 0; i--) {
                int c = word.charAt(i) - 'a';
                if (curr.isEmpty && !newWord) ans -= word.length() - i;
                if (curr.branch[c] == null) {
                    curr.branch[c] = new TrieNode();
                    newWord = true;
                    curr.isEmpty = false;
                }
                curr = curr.branch[c];
            }
            if (newWord) ans += word.length() + 1;
        }
        return ans;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
struct TrieNode {
    TrieNode *branch[26];
    bool isEmpty = true;
};

class Solution {
public:
    int minimumLengthEncoding(vector<string>& W) {
        TrieNode *trie = new TrieNode();
        int ans = 1;
        for (string word : W) {
            TrieNode *curr = trie;
            bool newWord = false;
            for (int i = word.size() - 1; i >= 0; i--) {
                int c = word[i] - 97;
                if (curr->isEmpty && !newWord) ans -= word.size() - i;
                if (!curr->branch[c]) {
                    newWord = true;
                    curr->branch[c] = new TrieNode();
                    curr->isEmpty = false;
                }
                curr = curr->branch[c];
            }
            if (newWord) ans += word.size() + 1;
        }
        return ans;
    }
};
```