I am redoing LeetCode design list. I am normally lazy and I don't like to do the things over and over. A Trie is required by a number of tasks at LeetCode, so this one fits all. Here is the list of the tasks I used this implementation to submit solutions for:
-
LeetCode 208 Implement Trie
-
LeetCode 3043 Find the Length of the Longest Common Prefix
-
not this yet, but maybe I will adopt some payload type mixin
#include "include/trie.hpp"
...
::containers::trie::of_int trie;
tries.insert(std::vector<int>{4, 2});
trie.find_word(std::vector<int>{4, 3});
trie.find_prefix(std::vector<int>{4}); //returns longest found prefix in a form of vector
std::vector<int>{4, 2} prefix;
trie.is_prefix(prefix.begin(), prefix.end(); //returns if a Container is a prefix
//...
::containers::trie::of_char trie_str;
::containers::trie::of_bool trie_bits;
// general declaration
// please pay attention GetIndexFunc should be noexcept
//
//template<typename T, typename GetIndexFunc, std::size_t ABCSize>
//using general = details::Trie<T, GetIndexFunc, ABCSize>;
auto get_index = [](char c) noexcept {return static_cast<std::size_t>(c - 'A');};
::containers::trie::general<char, decltype(get_index), 26u> trie_upper_chars;MIT
Despite heavy testing performed (see ./tests/data), no guarantees of any kind are given whatsoever. Use it at your own risk.