Questions tagged [trie]
A tree-like data structure used to hold an associative array, also called a Prefix Tree.
115
questions
2
votes
1
answer
69
views
Autocompletion trie for English words in zig
I am trying to write a program that creates a Trie from a list of all English words, and then when run provides completions for a given prefix. Basically for each node I allocate a list of 255 null ...
- 23
4
votes
1
answer
160
views
Trie implementation using std::shared_ptr
I've implemented a basic Trie that is supposed to work only with lowercase English letters.
...
- 153
5
votes
1
answer
126
views
Trie Implementation, Graph Visualization and Auto-Completion in C
Given a list of strings (say a text file containing some C symbols: c-symbols.txt), the program can:
Generate a graph of the underlying trie (-p/--prefix can be specified to inspect a
specific prefix ...
- 9,462
3
votes
1
answer
102
views
Autocomplete system with prefix tree
I am quite new to Haskell, and this problem is from dailycodingproblem.com:
Implement an autocomplete system.
That is, given a query string s and a set of all ...
- 33
0
votes
2
answers
86
views
Trie Data Structure in R7RS Scheme
Making the transition from R6RS Scheme to R7RS has been very educational and
fun. Chibi Scheme is my favorite because of its close compliance with the
standard.
When starting a new project, I wanted ...
- 247
3
votes
1
answer
130
views
Exceeded time limit on Trie search with Backtracking using Swift
I have been trying to solve Trie related problems over at leet code and came across this interesting problem 211. Design Add and Search Words Data Structure
Here is the question for convenience:
211. ...
- 253
5
votes
2
answers
572
views
Leet Code 139 (Word Break) using a trie with recursion
I was attempting to solve LeetCode 139 - Word Break
Given a string s and a dictionary of strings wordDict, return
...
- 253
2
votes
1
answer
204
views
Trie data structure in Swift lang
This is an implementation of a generic Trie DS, in Swift-lang, that is using however, for the sake of a easy example, strings.
It implements two operations, insert and search. So it can insert a text, ...
- 143
3
votes
1
answer
275
views
Lock-free, thread-safe trie container
This is a Trie data structure for mapping strings to integers or pointers in O(n) time. Based on the idea that we never delete anything from the container, we can perform concurrent read/write ...
- 421
0
votes
1
answer
159
views
Sorting in linear time using Trie Data Structure
I have written an article on a new way of non comparison sorting and I want it to get peer reviewed. The sorting algorithm uses Trie data structure to store digits of numbers as nodes and iterating ...
1
vote
1
answer
212
views
Comparing a prefix tree against a HashSet of strings in Java
Here, I have made an attempt to find out whether a prefix tree is any more efficient than a simple java.util.HashSet<String>. See what I have:
...
- 28.9k
3
votes
1
answer
96
views
Building a trie from a vector of strings in Rust
I'm learning rust (coming from C++) and playing around with different small algorithms to understand the ownership & borrowing concepts better. Currently, I'm having difficulties finding the ...
- 155
4
votes
1
answer
93
views
LetterDict, a dictionary whose keys must be lowercase letters [a-z]
Looking for any suggestions - alternative design, improvements to readability, improvements to the comments, etc.
I implemented this letter dictionary to see if it would faster than a regular ...
- 486
8
votes
1
answer
2k
views
Radix Tree Implementation in c
I tried implementing a radix tree using C language in order to get the auto complete suggestions of a dictionary. What are the improvements that I can do here? Also, is there any better way of doing ...
- 113
5
votes
0
answers
175
views
Binary PATRICiA Prefix Trie
I was wondering if we could speed-up lookup in a hash table of strings by only storing the difference between them, like HAMT. Taking this idea to its end, I ended up with a binary PATRICiA prefix-...
- 1,050