Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [trie]

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

5
votes
3answers
805 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
39 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
votes
1answer
83 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 ...
6
votes
2answers
170 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
95 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
284 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
324 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
85 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 ...
6
votes
1answer
514 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
50 views

Trie structure using Hash in Ruby

This is a follow-up to Boggle board solver in Ruby ...
2
votes
1answer
227 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
417 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
187 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
61 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
58 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. I followed @JDługosz recommendations. How does it look? Do you have any further recommendations? Is it better (if possible) to replace shared_ptr with unique_ptr? How could ...
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-...
6
votes
1answer
143 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
112 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
118 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
194 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
234 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
311 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
165 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
151 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
396 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
970 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
10k 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
6k 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 ...
8
votes
1answer
277 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
960 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 ...
4
votes
1answer
510 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 ...
-4
votes
1answer
89 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
552 views

A simple C++ Trie for working with strings

Here is a simple C++ 11 trie for insertion and membership testing: ...
5
votes
1answer
261 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
295 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 ...
4
votes
2answers
406 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
201 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 ...
2
votes
2answers
250 views

F#unctional Immutable Trie (Prefix Tree)

I've created the following implementation of a trie in F# as an effort to learn the language. I would like to know what could be done to make it more idiomatic. Any other pointers are welcome as well. ...
3
votes
1answer
89 views

Find the shortest whole repetitive substring (part 2)

This is a continued improvement from discussion here (Find the shortest whole repetitive substring), since code has changed a lot dues to improvement, I post it here. Major smart ideas are from ...
5
votes
4answers
1k views

Find the shortest whole repetitive substring

I'm working on a problem to find wholly repeated shortest substring of a given string, and if no match, return length of the string. My major idea is using a Trie ...
6
votes
2answers
761 views

Trie with insert, search, and startsWith methods for lowercase strings

I wrote the following prefix tree data structure for this Leet code challenge. Implement a trie with insert, search, and <...
4
votes
1answer
1k views

Trie Tree match string containing ? and *

Using Python 2.7 and here is my code which implement trie match for a whole word, and also support if the whole word contains ? (match any one character) or ...
1
vote
0answers
98 views

Efficient keyword trie implementation in C++ with failure/output links

For a current project implementing a parser for a bifurcation analysis tool, I wanted to utilize a keyword trie based solution, as there are possibly a ton of user supplied keywords. However, i found ...
10
votes
2answers
569 views

Spell checker using trie

This program implements spell checking by loading a given dictionary file into a trie structure and comparing against a given text file: ...
3
votes
3answers
582 views

Building prefix tree from dictionary, performance issues

I'm trying to build a prfix tree. So, using the following dictionary 'and','anna','ape','apple', graph should look like this: I've tried 2 approaches: using ...