Solution dùng trie beat 97%. Đang cố optimize thêm:
Một số trick đã dùng:
- Allocate trước memory cho tất cả các test case bằng biến static. Vì kích thước đầu vào là cố định nên có thể tính trước được tối đa lượng memory sẽ dùng. Lúc đó mỗi lần cần tạo một TrieNode mới thì chỉ cần dịch offset đi 26*8 byte. Cách này giải quyết được các nhược điểm cố hữu của Trie là phải allocate nhiều và bộ nhớ bị phân mảnh. Lúc này toàn bộ Trie đều nằm trên một khoảng liền, tổng dung lượng không quá 1.8 MB, có thể vừa khít trên L3 cache.
Cứ mỗi test case thì memset lại phần bộ nhớ tối đa có thể dùng. Con số này ước lượng dựa trên số từ đầu vào của test case đó.
- Tạm hoãn việc tạo TrieNode khi gặp một ký tự mới, thay vào đó gán bằng giá trị 0x1 để phân biệt với trường hợp bằng null (vì chắc chắn không con trỏ nào có giá trị 0x1). Chỉ khi nào xét đến con của node đó thì mới tạo.
Với cách allocate trước thì cách này có thể không cần thiết lắm, mà lại làm phức tạp code. Để thử bỏ đi làm theo kiểu bình thường xem có khá hơn không.
Sent from HUAWEI DBY-W09 using vozFApp
Một số trick đã dùng:
- Allocate trước memory cho tất cả các test case bằng biến static. Vì kích thước đầu vào là cố định nên có thể tính trước được tối đa lượng memory sẽ dùng. Lúc đó mỗi lần cần tạo một TrieNode mới thì chỉ cần dịch offset đi 26*8 byte. Cách này giải quyết được các nhược điểm cố hữu của Trie là phải allocate nhiều và bộ nhớ bị phân mảnh. Lúc này toàn bộ Trie đều nằm trên một khoảng liền, tổng dung lượng không quá 1.8 MB, có thể vừa khít trên L3 cache.
Cứ mỗi test case thì memset lại phần bộ nhớ tối đa có thể dùng. Con số này ước lượng dựa trên số từ đầu vào của test case đó.
- Tạm hoãn việc tạo TrieNode khi gặp một ký tự mới, thay vào đó gán bằng giá trị 0x1 để phân biệt với trường hợp bằng null (vì chắc chắn không con trỏ nào có giá trị 0x1). Chỉ khi nào xét đến con của node đó thì mới tạo.
Với cách allocate trước thì cách này có thể không cần thiết lắm, mà lại làm phức tạp code. Để thử bỏ đi làm theo kiểu bình thường xem có khá hơn không.
C++:
char ** offset;
class Solution {
static std::vector<char*> buffer;
#define NOTNULL(c) (long)c > Placeholder
#define ISNULL(c) (long)c <= Placeholder
struct TrieNode {
static constexpr long Placeholder = 1;
TrieNode * children = nullptr;
int addWord(std::string &s) {
auto *node = this;
int res = 0;
for (auto it = s.rbegin(); it != s.rend(); ++it) {
int first_time = 0;
int divergence = 0;
if (ISNULL(node->children)) {
node->children = (TrieNode*) offset;
offset += 26;
//std::memset(children, 0, 26 * sizeof(TrieNode*));
first_time = 1;
}
auto &pc = node->children[*it - 'a'];
if (pc.children == nullptr) {
pc.children = (TrieNode*) Placeholder;
divergence = first_time ? 0 : (it - s.rbegin() + 2);
}
res += first_time + divergence;
node = &pc;
}
return res;
}
};
public:
Solution() {
if (buffer.size() == 0) {
int sz = 2000;
buffer.resize(26 * (1 + min(sz, 26) + min(sz, 26*26) + sz * 4));
}
}
int minimumLengthEncoding(vector<string>& words) {
int sz = words.size();
offset = buffer.data();
std::memset(offset, 0, sizeof(char*) * 26 * (1 + min(sz, 26)
+ min(sz, 26*26) + sz * 4));
//buffer.resize(26 * (1 + min(sz, 26)
// + min(sz, 26*26) + sz * 4));
int res = 1;
TrieNode root;
for (auto &w : words) {
res += root.addWord(w);
}
return res;
}
};
std::vector<char*> Solution::buffer;Sent from HUAWEI DBY-W09 using vozFApp
