题目描述
标准解法 字典树Trie $O(\Sigma wi)$
本题的核心就是如何找到是其他单词后缀的单词并删去。利用字典树，反向插入单词。这样后缀相同的单词在同一棵子树中，巧妙地过滤了需要删去的单词。最后只需要统计叶子所有叶子节点的高度，即为所求。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class TrieNode{
TrieNode* children[26];
public:
int count;
TrieNode() {
for (int i = 0; i < 26; ++i) children[i] = NULL;
count = 0;
}
TrieNode* get(char c) {
if (children[c - 'a'] == NULL) {
children[c - 'a'] = new TrieNode();
count++;
}
return children[c - 'a'];
}
};
class Solution {
public:
int minimumLengthEncoding(vector<string>& words) {
TrieNode* trie = new TrieNode();
unordered_map<TrieNode*, int> nodes;
for (int i = 0; i < (int)words.size(); ++i) {
string word = words[i];
TrieNode* cur = trie;
for (int j = word.length() - 1; j >= 0; --j)
cur = cur->get(word[j]);
nodes[cur] = i;
}
int ans = 0;
for (auto& [node, idx] : nodes) {
if (node->count == 0) {
ans += words[idx].length() + 1;
}
}
return ans;
}
};
|
个人解法 暴力
按照题意填充#并查找判断。其中find的开销最大。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| inline int cmp(const string& s1, const string& s2)
{
return s1.length() > s2.length();
}
class Solution {
public:
int minimumLengthEncoding(vector<string>& words) {
string zipstr = "";
sort(words.begin(), words.end(), cmp);
for (auto str : words)
{
if (zipstr.find(str + "#") == zipstr.npos)
{
zipstr += str + "#";
}
}
cout << zipstr << endl;
return zipstr.length();
}
};
|
总结
- 可以用
auto& [key, value]来遍历map中的pair，很简洁的写法
- 尽量别一想到暴力就用，往深考虑更优的解法。同时记住一些通用的解法，比如这次的字典树。
