1,112
questions
0
votes
0
answers
71
views
C++ Prefix trie wildcard matching
I'm trying to implement a url wildcard matching in prefix trie on C++.
For example:
url hello.world.com - (matches) world.com
h?llo.world.com - world.com
h?llo.w*rld.com - test.world.com, world.com
...
0
votes
0
answers
43
views
How to implement common prefix search by using Apache Commons Trie?
Given a string, I want to return all strings in a trie that prefix the given string. So if a trie contains the strings "ae" and "b", trie.searchCommonPrefix('aeb') should return a ...
-3
votes
1
answer
77
views
Longest Common Prefix implementation works fails test case on LeetCode
I'm trying to solve LeetCode problem 14. Longest Common Prefix:
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty ...
1
vote
2
answers
141
views
Check if there are 3 numbers in array whose XOR is equal to zero
Given array of N real numbers x_1, x_2, ..., x_n, check if there exists 1 <= i,j,k <= n such that x_i ⊕ x_j ⊕ x_k = 0, where ⊕ is XOR operation.
This is college homework and it has to be done in ...
1
vote
1
answer
74
views
Using pygtrie, how do you find all the words in some text that have been added to a trie?
If I have...
from pygtrie import Trie
trie = Trie()
trie["Grand Canyon"] = true
trie["New York"] = true
How do I search the trie such that it returns all the key names found in ...
3
votes
2
answers
271
views
Design Add and Search Words Data Structure: Leetcode 211
I am currently trying to solve the problem Add and Search Words Data Structure on leetcode. The question is as follows:
Design a data structure that supports adding new words and finding if
a string ...
0
votes
0
answers
57
views
How there is Multiple map elements in single index of vector of map
In my main function, I use the variable t of type trie, which is a vector of maps:
#include <string>
#include <iostream>
#include <vector>
#include <map>
#include <utility&...
1
vote
2
answers
535
views
Pick K letters to build as many strings as possible
I stumbled upon this question and I'm unable to solve it. Any help is much appreciated.
You are given an array S made of N strings and an integer K. Choose at most K letters from the alphabet that ...
0
votes
0
answers
59
views
Firebase enabled Trie search doesn't give result on already searched text
I'm currently working on an Android application where I need to implement real-time search functionality using Firebase Database. I've set up a Trie data structure to efficiently search through user ...
0
votes
1
answer
47
views
Using package @ethereumjs and having 'invalid transaction trie'
I'm trying to create a sequence of block for a blockchain with the ethereumjs-monorepo.
Those are the versions i'm using
"@ethereumjs/block": "^5.0.1",
"@ethereumjs/blockchain&...
0
votes
0
answers
52
views
The theoretical complexity of Tries and the distances of Levenshtein to suggest similar words
Could someone explain me about the complexity of Trie and the algorithm of the distance of levenshtein? For tries my professor, has one image that says the complexity of it is O(k(logm +1)) where k is ...
0
votes
1
answer
164
views
What is the purpose of using a helper function to build nodes for data structures like tries and linked lists?
I've been working on Leetcode questions trying to improve my coding skills and I became curious about this when doing this problem https://leetcode.com/problems/implement-trie-prefix-tree/
Most ...
1
vote
1
answer
80
views
How to build a prefix trie for fast prefix text search, using data from a Hunspell dictionary, without precomputing all derived word forms?
I am looking at a sample Hunspell dictionary like this Sanskrit one (or this 800,000+ line zip file one), which has stuff like this:
युयुक्ष्ये/3,4,33,34,53,63,76,86,88,94,158,178,179,182,184,185
...
1
vote
1
answer
372
views
"Process finished with exit code 139 (interrupted by signal 11: SIGSEGV)" In CLion
While trying to solve a coding problem today, I got tired of OnlineGDB not being able to support large input files, so I decided to pull out CLion and use that instead. However the result that I get ...
0
votes
0
answers
57
views
Search string instantly by JTextField and JList
I'm making a dictionary application, which has a search function. When we type something to the textfield, we want receive a list result in the JList instantly, but I can't make it has been done ...
1
vote
0
answers
100
views
How to Implement Trie Delete Function Without Overlapping Error
I'm trying to implement a Trie in c++ in order to solve this problem https://codeforces.com/problemset/problem/706/D, and I've gotten everything down except for the delete function. For some reason, ...
0
votes
1
answer
170
views
Implementing Trie dictionary with dictionary children for Boggle game in Python 3.x
import typing
from typing import Optional, Dict
from collections.abc import Iterator
class TrieNode:
def __init__(self):
self.children: Dict[str, TrieNode] = {} # maps a child ...
1
vote
0
answers
94
views
Acronym finder which also scan characters inside a word
I am trying to make an acronym generator which can generate acronym from characters not only from the first character of word but also character inside a word. I did some programming in Java (https://...
1
vote
0
answers
65
views
How to retrieve specific matches from Trie search results in Python?
I have implemented a Trie data structure in Python to search for words or phrases in long texts. The Trie contains a dataset of words/phrases with associated categories. My goal is to find specific ...
0
votes
1
answer
53
views
Can't figure out why my CSV file is not converting to a string when adding to trie node
Reading in a basic csv file, the first line,(csv), is "abacus,,,,,,,, trust,,". Trying to take out the commas and add the two words to some sort of list or array. The issue starts when I try ...
0
votes
1
answer
114
views
How to deal with all deletes in Trie Implementation in C++
struct Trie {
struct TrieNode {
bool isEnd;
array<TrieNode*, 26> child;
TrieNode() : isEnd(false), child{} {}
bool isEmpty() {
...
2
votes
1
answer
288
views
CS50 Trie Week 5: check function not working
I have been trying to complete the trie practice problem from the CS50 course. The check function that I wrote must check whether the user input is found within the trie that has been created in the ...
0
votes
1
answer
91
views
How does this code work and not crash or seg fault?
So this question is a bit different, the code works I just don't know why or how.
I'm taking the CS50 course and I'm solving this practice problem aiming at training us at searching tries databases. ...
0
votes
0
answers
140
views
When implementing Trie Data Structure using smart pointer is it necessary to use shared pointers?
Link to gfg: Trie Data Structure using smart pointer
I came across this implementation of Trie Data Structure using shared pointers. But I don't understand the purpose of using shared pointers.
Can we ...
0
votes
1
answer
58
views
NULL values are being reassigned to garbage at runtime
I have a C program to implement of Trie in which each not stores some data (see below). The trie should use strings in it's branches to arrange data (ie as keys) with integer data at each terminating ...
0
votes
1
answer
35
views
Unexpected error in Trie delete string method
I am trying to build a method to delete a string from Trie , when i run the code it says the following error despite the fact that everything is correct ( according to me ) whats the error in my code
...
-2
votes
1
answer
218
views
Maximum XOR with all possible subsets of an array with a specific integer
Given an array of integers P = [P1, P2, ...] and a function F(M) that returns the XOR of all integers present in set M. If M is empty, then F(M) = 0.
The task is to find the maximum possible value of ...
1
vote
1
answer
52
views
Is there an existing Data Structure like this? ( A modified Trie )
I have been working on trie data structure recently and an alternative immediately struck to me.
For example :
This is a trie with 2 words : football and goofball.
This is the alternate data structure ...
2
votes
1
answer
320
views
How to create slice of LPM trie record for IPs/CIDRs
I am trying to use the BatchUpdate and BatchDelete API from https://github.com/cilium/ebpf/blob/master/map.go#L952-L1038. from my understanding, I need to create slice of LPM trie of IPs/CIRDs, for ...
0
votes
1
answer
455
views
How to iterate over each word in a Trie using __iter__()and __next__() functions and generators in Python
I have a Trie that is structured below. I am trying to write an iterator and next function that will iterate over each word in the Trie and then raise StopIteration once it is completed but I'm ...
-1
votes
1
answer
87
views
c++: segmentation fault for Trie data structure [closed]
I am a noobie to c++ and I'm recently learning trie data structure. As I was implementing the header file for the Trie, I've encountered segmentation fault that I cannot resolve. I used the typical ...
0
votes
0
answers
157
views
How to calculate the time complexity for Leetcode's Longest Common Prefix with a solution using Tries
I am trying to improve my problem solving skills, and have solved problem #14 in Leetcode "Longest Common Prefix" using the Trie data structure.
My solution runs in 106ms and beats 42.91%. ...
0
votes
3
answers
281
views
Python Trie implementation - Inserting elements into a trie recursively
I have implemented a trie tree using a list in Python which stores words.
I am trying to write a function that insert words into a trie recursively.
Here my trie class and the function insert() :
...
0
votes
1
answer
89
views
Is there an alternative to Trie for my needs?
I have a program that requires an ID to load a template.
The template is assigned based on the ID. Each template has a key, e.g. tx. IDs that contain this pattern will have this template assigned, e.g ...
0
votes
0
answers
545
views
How do I implement a memory arena allocator to reduce memory request calls in a trie-based spell checker?
As part of the cs50x course, I made a trie-based dictionary spell checker that passes all of check50's tests as well as valgrind so no memory errors. Now I'm trying to implement a memory bucket to ...
0
votes
1
answer
49
views
why the pointer is not incrementing at line 27
i am implementing the trie data structure, why my pointer is not incrementing at line# 27. all the characters are getting into forst node only.
this is my code
class Trienode:
data:str
next:...
2
votes
1
answer
584
views
Why isn't bitwise trie a popular implementation of associative array
I have to store billions of entries with Int64 keys in an ordered map.
If I use a usual BST then each search operation costs log(N) pointer dereferencings (20-30 for millions to billions entries),
...
0
votes
0
answers
324
views
How to specify a lifetime for a borrow in a struct in Rust?
I have a Trie struct whose nodes have children which are also nodes:
pub struct Trie<'a, T: marker::Copy> {
nodes: [Option<TrieNode<'a, T>>; MAX_NODE_LEN],
min_len: usize,
...
1
vote
0
answers
56
views
How would a patricia tree look like after adding a word that starts as the substring of another but has additional letters?
Take this trie as example:
I want to add the word "luan" to this representation, but luan takes 20 bits to represent, while lua takes 15. So, they "differ" from each other on the ...
0
votes
1
answer
23
views
Unset element from trie using reference
I am having some difficulties to delete empty parent node if empty from a trie. I can correctly identify the node that has the value 3, but then I cannot unset nodes that do not have any children.
...
0
votes
2
answers
433
views
Algorithm to find all duplicate sequences of tokens in a long string
Let's say I have a really long string consists of 10^6 tokens (for simplicity, token is a space-separated word, so this string is splitted to list of tokens)
now I need to find all possible duplicated ...
0
votes
0
answers
104
views
Longest Common Substring from Trie
i'm trying to obtain the longest common substring from two strings and have coded a trie, but im not too sure how to obtain the longest common substring based on this trie. Could someone please help, ...
-1
votes
1
answer
40
views
why my code doesn't change the head value in c# or i have to use somethings like pointers?
ok, guys, so I was doing the ReplaceWord problems from leetcode in c# ! and I had to initialize a prefix tree. the reason why I use c# that because it has split method which c++ doesn't have.the ...
0
votes
1
answer
30
views
Why are the Trie Functions unable to produce my desired output?
Your task is to create a trie system that is hosted online with a global state that supports multiple concurrent clients and the following operations:
Add keyword to trie
Delete a keyword from trie
...
0
votes
1
answer
95
views
What is the problem with fill() here ? I used normal for loop for assigning NULL and it worked , with fill() it was giving error
The code below is a Trie implementation in C++. Kindly checkout what is the problem in using fill(). And if any suggestions improving my implementation are welcome
Commented fill() in the TrieNode ...
-1
votes
2
answers
171
views
How to return an int within a trie in python
I'm trying to search for a word within my trie data structure and if it exists in the trie, return the word and its frequency.
This is what the trie looks like:
{'c': {'u': {'t': {('e', 10): True, ('s'...
-1
votes
5
answers
577
views
how to write a function that returns all elements with same attribute from domtree?
I saw somewhere that this question was asked in a faang interview and I cannot come up with an optimized solution or find it anywhere. So the question basically wants us to write a function that ...
1
vote
0
answers
300
views
Difference between a patricia trie (radix tree with r = 2) and a binary trie?
I am trying to consolidate my understanding of the difference between a patricia trie (radix tree with r = 2) and a binary trie. As far as I can see the implementation of a binary trie and a patricia ...
-1
votes
2
answers
77
views
What is wrong with my trie suggestion algorithm?
I am coding an algorithm that uses the trie data structure. Basically, if input is "he", it will return ["hello","help","held","hen",...
0
votes
1
answer
105
views
Leetcode Testing of Trie Results Don't Match Local NodeJs Output
Description:
I implemented a [Trie on Leetcode][1] and when I test it locally, running Node v16.15.1, the output of the test case I get does not match the output on LeetCode.
I ran the initial test ...