题目
原题在此
解析
因为题中说到words.size() <= 7, 所以可以按照字符串长度给words排序, 复杂度几乎可以忽略不计. 之后再逐个尝试插入即可.
当words.size()很大时, 就需直接用前缀树了.
代码
c++
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
| class Solution {
public:
const static int N = 14007;
int idx = 0;
int map[N][26];
bool insert(string &s) {
int p = 0;
bool res = true;
for(int i = s.size() - 1; i >= 0; i--) {
int u = s[i] - 'a';
if(map[p][u] == 0) {
map[p][u] = ++idx;
res = false;
}
p = map[p][u];
}
return res;
}
int minimumLengthEncoding(vector<string>& words) {
sort(words.begin(), words.end(),
[](const string & a, const string & b) -> bool {
return a.size() > b.size();
});
int res = 0;
for(auto & word : words) {
if(!insert(word)) res += word.size() + 1;
}
return res;
}
};
|
前缀树模板
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
| class Trie {
private:
bool is_string = false;
Trie* next[26] = { nullptr };
public:
Trie() {}
void insert(const string& word) {
Trie* root = this;
for (const auto& w : word) {
if (root->next[w - 'a'] == nullptr)root->next[w - 'a'] = new Trie();
root = root->next[w - 'a'];
}
root->is_string = true;
}
bool search(const string& word) {
Trie* root = this;
for (const auto& w : word) {
if (root->next[w - 'a'] == nullptr)return false;
root = root->next[w - 'a'];
}
return root->is_string;
}
bool startsWith(const string& prefix) {
Trie* root = this;
for (const auto& p : prefix) {
if (root->next[p - 'a'] == nullptr)return false;
root = root->next[p - 'a'];
}
return true;
}
};
|