Questions tagged [trie]

A tree-like data structure used to hold an associative array, also called a Prefix Tree.

Filter by
Sorted by
Tagged with
4
votes
1answer
67 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 ...
1
vote
1answer
91 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 ...
4
votes
1answer
70 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 ...
3
votes
1answer
73 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 ...
4
votes
1answer
74 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 ...
2
votes
1answer
112 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, ...
3
votes
1answer
130 views

Add and Search Word

This is a Leetcode problem: Design a data structure that supports the following two operations: void addWord(word) ...
2
votes
1answer
80 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
votes
3answers
830 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 ...
2
votes
1answer
54 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: ...
6
votes
1answer
102 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 ...
5
votes
2answers
223 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 ...
3
votes
0answers
157 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 ...
6
votes
1answer
388 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 ...
4
votes
0answers
479 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-...
2
votes
2answers
99 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 ...
7
votes
1answer
920 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 ...
1
vote
1answer
60 views

Trie structure using Hash in Ruby

This is a follow-up to Boggle board solver in Ruby ...
2
votes
1answer
287 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 ...
4
votes
3answers
459 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 ...
3
votes
1answer
207 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. ...
3
votes
1answer
69 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. ...
3
votes
0answers
63 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 ...
11
votes
2answers
2k 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 ...
5
votes
2answers
3k 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-...
5
votes
1answer
160 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 ...
7
votes
2answers
124 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 ...
4
votes
1answer
121 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 ...
6
votes
1answer
210 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, ...
2
votes
0answers
243 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 "...
1
vote
1answer
366 views

Generic trie implementation in Java

I implemented a Trie data structure in Java, to test my understanding of the concept. I tried (pun intended :) ) to follow TDD steps along the way (i.e., add first a failing test case, and implement ...
1
vote
0answers
177 views

Radix trie optimization

I have got a list of Users that I want to filter using text typed in TextView. I want it to be a smart filter, something like searching contacts in contact book on ...
4
votes
2answers
164 views

Using a radix tree to find case-insensitive matches in large files

I'm using a radix tree library to find case-insensitive matches from several relatively large files (~24 files each on the order ~150MB). My current algorithm requires me to read the chars of an ...
6
votes
3answers
408 views

Trie implementation in C++

I would like to know if my implementation of a Trie data structure which supports addition, search and deletion of words is considered standard/optimal. More specifically, I have used a Hashmap in ...
11
votes
2answers
1k views

Trie data structure in C++ with add and search

I am learning C++11 and wanted to practice data structures so here is my trie implementation with add and search functions. What are some things to improve? trie.h ...
5
votes
2answers
12k views

Find all words in a dictionary that can be made with a string of characters (Recursion/Binary Search)

I'm working on an algorithm that could take in a string of 20 random characters, and display to the user every word in a dictionary that can be successfully made with those letters, regardless of ...
1
vote
0answers
54 views

Searching for a word

The searchWord function needs to be able to traverse the tree and test if a word is there, which it does, but I wanted some opinions on if this is a more complex ...
6
votes
2answers
7k views

C++ Trie using std::map and std::unique_ptr

I'm learning C++ and whilst trying to write in modern C++, I've made an attempt to rewrite a trie implementation written in C found here: http://www.geeksforgeeks.org/trie-insert-and-search/ It uses ...
9
votes
1answer
299 views

Trie implementation for a data structure library in C

I'm implementing a trie structure for a library, as an exercise in data structures. Details The tree structure is represented as a doubly chained tree. A struct ...
2
votes
3answers
1k views

Loading dictionary words into a trie

I have here a program created for pset5 of the CS50 course. The program compiles correctly and does as it should. However, is there any way to improve the run time of this program? Are there any ...
3
votes
1answer
534 views

A Trie data structure in Java

this is the first time I' implementing a Trie. My goal was to make it as simple as possible. So here is the result: Can I simplify anything else? Are there some things I can change to increase ...
-3
votes
1answer
92 views

Search function for a trie tree

I have made a search function that seems to work for passing the tester. I am just unsure if it will always be without errors. Can someone tell me if they see any flaws in the logic, and if so, where ...
2
votes
2answers
603 views

A simple C++ Trie for working with strings

Here is a simple C++ 11 trie for insertion and membership testing: ...
5
votes
1answer
277 views

Insert function for a trie in Ocaml

I don't know how could I write smarter/more elegant code for the add function , it just seems so meaty and hard to read. This trie only stores words and marks their ...
4
votes
1answer
334 views

Hackerrank: Prefix neighbors

Problem statement Mark has a dictionary, S, containing n distinct strings. He defines the benefit value of a string as the ...
6
votes
2answers
3k views

Prefix search by trie tree

I'm working on the prefix search problem: Given a set of words, for example words = ['a', 'apple', 'angle', 'angel', 'bat', 'bats'], for any given prefix, find ...
3
votes
2answers
413 views

Implementation of Trie Structure

I want to improve this code. I know I'm not fully utilizing the data structure. (This is not a homework assignment, I finished and passed the class this fall semester). I would really like to know for ...
15
votes
1answer
2k views

Trie implementation in Python

I have created a trie in Python and am looking for feedback. Specifically, I am looking for feedback on: If my code is 'pythonic' If my logic is proper when inserting and retrieving from the trie I ...
7
votes
2answers
3k views

Split string to space-separated words based on dictionary

This program is based on as old retired Google interview question where you're supposed to create a program that will split a string into space-separated words, if the string is composed of valid ...
1
vote
1answer
226 views

Trie-based spell checker

This is a classic problem with a classic solution and I've seen it a number of times on this site, but I wanted to know what people thought of this C# implementation, as opposed to the numerous C ...