Problem
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 <= words.length <= 2000.
1 <= words[i].length <= 7.
- Each word has only lowercase letters.
Idea
Remove all the words that are suffix of other words.
Solution
Time complexity: O(n*l^2)
Space complexity: O(n*l)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua // Running time: 43 ms class Solution { public: int minimumLengthEncoding(vector<string>& words) { unordered_set<string> s(words.begin(), words.end()); for (const string& w : words) { for (int i = w.length() - 1; i > 0; --i) s.erase(w.substr(i)); } int ans = 0; for (const string& w : s) ans += w.length() + 1; return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment