Questions tagged [trie]
A tree-like data structure used to hold an associative array, also called a Prefix Tree.
116 questions
3
votes
1
answer
79
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 ...
- 33
4
votes
1
answer
166
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
128
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,777
8
votes
3
answers
944
views
Simple tree dictionary structure in C
I have developed a C library whose goal is to store strings in an easily searchable tree structure (which I have dubbed tree-dictionary). I come from a math background and I have been coding in Python ...
3
votes
1
answer
113
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
95
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
131
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
585
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
205
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
279
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
163
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
215
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:
...
- 29.8k
3
votes
1
answer
97
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
96
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
178
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,080
2
votes
0
answers
150
views
2
votes
1
answer
258
views
Trie implementation for strings in Swift
A trie for handling strings for an autocomplete dictionary. This passes my fairly casual tests, though it's always possible that there are broken edge cases, but I'm mainly concerned about design and ...
- 295
5
votes
1
answer
101
views
C++ simple dictionary match and insert, unique_ptr, operator<
I'm learning C++ and did some reading here and elsewhere on trie structures. I've written a simple class that performs insert and match using a sorted vector as the underlying container.
I used ...
- 53
0
votes
2
answers
822
views
Finding the k most frequent words in file in c++
I have written C++ code using trie and min-heap to find the k most frequent words. I want to review my code.
...
- 21
5
votes
1
answer
2k
views
Count words with given prefix using Trie
I have been trying to solve this HackerRank problem:
We're going to make our own Contacts application! The application must perform two types of operations:
add name, where is a string denoting a ...
- 493
1
vote
1
answer
1k
views
Boggle using Trie and DFS
I already mentioned in my previous code review, there are two solutions for this problem
https://www.geeksforgeeks.org/boggle-find-possible-words-board-characters/
this is the first:
Find all ...
- 5,253
4
votes
1
answer
147
views
Binary Trie in F#
I have this little exercise writing a binary trie in F#. In C# it can be done in few lines, but here it became more complicated than I had expected (especially the ...
user73941
3
votes
1
answer
1k
views
Boggle solver - Updated (with Trie)
Here is an update to my previous boggle solver. The new version has an almost instantaneous output, removing the need to limit the length of words being searched for.
Any comments on my general ...
- 2,053
4
votes
1
answer
769
views
Non-recursive version of Trie deletion [closed]
So,I was looking for the non-recursive version of Trie data structures deletion in the internet. I couldn't find one. The best I could manage to find was a recursive implementation of trie in this ...
- 205
2
votes
1
answer
298
views
LeetCode: Maximum XOR of Two Numbers in an Array
Please review how clear my code is and also comment on performance.
Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai
< 2^31.
Find the maximum result of ai XOR aj, ...
- 5,253
5
votes
1
answer
227
views
LeetCode: Add and Search Word C#
This is a Leetcode problem:
Design a data structure that supports the following two operations:
void addWord(word)
...
- 5,253
2
votes
1
answer
209
views
LeetCode: Replace Words Trie C#
I am trying to solve this leet code problem
https://leetcode.com/problems/replace-words/
Please comment about performance.
In English, we have a concept called root, which can be followed by
...
- 5,253
5
votes
3
answers
932
views
Leetcode: Map Sum Pairs C#
Implement a MapSum class with insert, and sum methods.
For the method insert, you'll be given a pair of (string, integer).
The string represents the key and the integer represents the value. If
...
- 5,253
2
votes
1
answer
205
views
LeetCode: Trie Tree implementation, Search, Insert, startWith C#
https://leetcode.com/problems/implement-trie-prefix-tree/
Please comment about performance and style.
Implement a trie with insert, search, and startsWith methods.
Example:
...
- 5,253
6
votes
1
answer
321
views
Phonebook using a trie
I implemented a PhoneBook utilizing a Trie data structure.
Could I ask you to evaluate it?
Did I apply Trie correctly for such ...
- 218
6
votes
2
answers
1k
views
Scrabble Solver
The start of a simple Scrabble solver.
What I have so far:
Add a word to the trie
Return a sorted list with the all possible combinations, based on the letters input
Some basic tests
Edit
Since ...
- 11.6k
3
votes
1
answer
542
views
Looking for words from a list of words in a sentence
Problem
Given a Dictionary with user_id and a list of alert_words (words
and phrases too look for in an sentence) and a ...
- 1,158
6
votes
1
answer
1k
views
Trie Implementation in C++11
I implemented a Trie in C++11, but I am not sure if my usage of struct and std::unique_ptr, and ...
- 163
7
votes
1
answer
2k
views
Trie (dictionary tree) data structure implementation: insertWord, printAllWords, searchPrefix, deleteWord, deleteTrie
This Trie implementation works, however, I would like to get an advice on how to improve this code.
Any advice is appreciated: functions implementation, memory management, modern C++ usage, const-...
- 313
2
votes
2
answers
8k
views
Hacker Rank: Counting names with prefix matches using a trie
Practicing hacker rank questions and would love some feedback on how I could perform optimizations on a Trie.
This code will add a bunch of names into a trie and then when asked will turn how many ...
- 195
7
votes
1
answer
2k
views
Implementing a Trie in Python
Question:
Implement a trie with insert, search, and startsWith methods.
Source:
https://leetcode.com/problems/implement-trie-prefix-tree/description/
The Trie object will be instantiated and ...
- 93
1
vote
1
answer
260
views
2
votes
1
answer
1k
views
C++ - Trie Implementation
I am trying to learn trie and this is my first implementation. I started off with the idea of being able to handle different data types for key and value; however, I found the data structure a bit ...
- 539
4
votes
3
answers
2k
views
Simple trie class in C++
I would be very grateful to get some thoughts on this toy-implementation of a trie that I wrote to practice my C++.
Some questions I have:
Is my create member ...
- 143
3
votes
1
answer
625
views
Autocomplete implementation in Python
I have an autocomplete implementation in Python, and it passed all of the unit tests that I have included at the bottom.
...
- 2,489
3
votes
1
answer
198
views
Readable implementation of Trie in Python
Need reviews on my readable implementation of Trie. Also what other methods can or should be added to this data structure.
...
- 351
4
votes
0
answers
148
views
C++ Trie implementation with Python wrapper
I'm just starting to use C++ so beginner feedback is fine here.
CPP code
(main.cpp, node.h, node.cpp, trie.h, trie.cpp, utils.h)
main.cpp
...
- 501
11
votes
2
answers
3k
views
Trie Data Structure Implementation in C++11 using Smart Pointers -- follow-up
Link to my first question.
Link to my latest source code.
I followed @JDługosz recommendations. How does it look? Do you have any further recommendations? Is it better (if possible) to replace ...
user151056
5
votes
2
answers
4k
views
Trie Data Structure Implementation in C++11 using Smart Pointers
This implementation is part of my open source project forest.
I wrote the following header file to implement a trie data structure that supports inserting and searching strings consisting of 26 lower-...
user151056
5
votes
1
answer
429
views
Trie based string indexing with edit distance / Levenshtein in Go
This is my first Go program that I've ever written. The code can also be found here.
It allows you to create a search index and add words to it. The twist is that when searching for a word within the ...
- 153
7
votes
2
answers
218
views
Trie implementation with Python 3
This is just a classic implementation of a trie using python 3.6, with types. I am a PHP developer, so these are my first attempts with Python.
I know I can improve the readability of my code, it's a ...
- 173
3
votes
1
answer
170
views
Levenshtein Distance of transitively similar words
The code's purpose is this: Two words are friends if they have a Levenshtein distance of 1. That is, you can add, remove, or substitute exactly one letter in word X to create word Y. A word’s social ...
- 39
6
votes
1
answer
580
views
Dictrie: Extending the Python dictionary into a Trie
I implemented a trie in Python2.7 as a dictionary of dictionaries by extending the UserDict class to allow native dictionary access syntax and iteration.
For example, ...
- 63
2
votes
0
answers
286
views
Learn trie through Leetcode 212
Problem statement:
Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must be constructed from letters of sequentially adjacent cell, where "...
- 2,396