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.

4
votes
1answer
64 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
133 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
66 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
176 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
194 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
80 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 ...
5
votes
1answer
198 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 ...
0
votes
1answer
39 views

Trie structure using Hash in Ruby

This is a follow-up to Boggle board solver in Ruby ...
2
votes
1answer
168 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
374 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
176 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
49 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
57 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
1k 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
2k 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
108 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
102 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
101 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
177 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
216 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
263 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
147 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
147 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
388 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
920 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
9k 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
5k 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
248 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
903 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
476 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
81 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
469 views

A simple C++ Trie for working with strings

Here is a simple C++ 11 trie for insertion and membership testing: ...
5
votes
1answer
240 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
282 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
2k 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
384 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
176 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
241 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
705 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 <...
3
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
95 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
499 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
550 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 ...
3
votes
0answers
723 views

Inserting nodes into a trie data structure

I have a recursive algorithm that inserts nodes into a trie data structure but it seems to be running not well and takes over 10 mins to complete on a data set of about 1 million. All nodes contain a ...
4
votes
1answer
154 views

Char Trie and scanner in one

This is from the Resin codebase. It is fast at lookup but I could use some help making it faster at buildup. Loaded with 210K words, it looks up pretty much any node and its descendants in zero time. ...