820 Short Encoding of Words
my solution = =
一开始先试着用 O(n2) 的方法, 之后用 O(n), 但是时间依旧很长
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int minimumLengthEncoding(vector<string>& words) {
sort(words.begin(), words.end(), [](string &str1, string &str2) {
return str1.size() > str2.size();
});
string str;
for (int i = 0; i < words.size(); i++) {
if ( str.find(words[i] + '#') == string::npos ) {
str.append(words[i] + '#');
}
}
return str.size();
}
};
|
并且这个代码之前还踩了个坑 : https://www.boost.org/sgi/stl/StrictWeakOrdering.html
best solution
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
| class Solution {
public:
int minimumLengthEncoding(vector<string>& words) {
for (string& s : words) {
reverse(s.begin(), s.end());
}
sort(words.begin(), words.end());
int length = 0;
int i = 0;
while (true) {
if ((i + 1) >= words.size()) {
length += words[i].length() + 1;
break;
}
if (words[i+1].compare(0, words[i].length(), words[i]) != 0) {
length += words[i].length() + 1;
}
i++;
}
return length;
}
};
|
em… 逻辑挺简单的
反序字符串, 字典序排序, 后再直接 compare