# 820. Short Encoding of Words

Given a list of words, we may encode it by writing a reference string `S` and a list of indexes `A`.

For example, if the list of words is `["time", "me", "bell"]`, we can write it as `S = "time#bell#"` and `indexes = [0, 2, 5]`.

Then for each index, we will recover the word by reading from the reference string from that index until we reach a `"#"` character.

What is the length of the shortest reference string S possible that encodes the given words?

Example:

``````Input: words = ["time", "me", "bell"]
Output: 10
Explanation: S = "time#bell#" and indexes = [0, 2, 5].
``````

Note:

1. `1 <= words.length <= 2000`.
2. `1 <= words[i].length <= 7`.
3. Each word has only lowercase letters.

``````class Solution {
public:
int minimumLengthEncoding(vector<string>& words) {
string str = "";
sort(words.begin(), words.end(), [](string& a, string& b){return a.size() > b.size();});
for (string word : words) {
int found = str.find(word);
if (found == string::npos || str[found + word.size()] != '#') {
str += word + "#";
}
}
return str.size();
}
};
``````

``````class Solution {
public:
int minimumLengthEncoding(vector<string>& words) {
int res = 0, n = words.size();
for (int i = 0; i < n; ++i) reverse(words[i].begin(), words[i].end());
sort(words.begin(), words.end());
for (int i = 0; i < n - 1; ++i) {
res += (words[i] == words[i + 1].substr(0, words[i].size())) ? 0  : words[i].size() + 1;
}
return res + words.back().size() + 1;
}
};
``````

``````class Solution {
public:
int minimumLengthEncoding(vector<string>& words) {
int res = 0;
unordered_set<string> st(words.begin(), words.end());
for (string word : st) {
for (int i = 1; i < word.size(); ++i) {
st.erase(word.substr(i));
}
}
for (string word : st) res += word.size() + 1;
return res;
}
};
``````

https://leetcode.com/problems/short-encoding-of-words/

https://leetcode.com/problems/short-encoding-of-words/discuss/125825/Easy-to-understand-Java-solution

https://leetcode.com/problems/short-encoding-of-words/discuss/125822/C%2B%2B-4-lines-reverse-and-sort

https://leetcode.com/problems/short-encoding-of-words/discuss/125811/C%2B%2BJavaPython-Easy-Understood-Solution-with-Explanation

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation