wat exaclty the question is..... We have to make a tire with filter or we have a trie(whole dictionary) and we have to check filter out the elements.
plz explain question On Wed, May 29, 2013 at 7:55 PM, Don <[email protected]> wrote: > There has to be some way to know that a node is the end of a word, and > to know what that word is. This might be done by using a parent > pointer which lets you traverse the trie back to the root, rebuilding > the word, or you could keep track of the word as you traverse down the > trie. Putting the whole word in the node where the word ends would be > the most simple and time-efficient approach, if you have the memory to > support it. > > Here is a different way to do it, if the trie has a "wordEnd" flag and > does not store the word in the node. > > void findWords(trie *root, char *filter, String word="") > { > if (!root) return; > > if (*filter == 0) // When you reach the end of the filter at the > end of a valid word, add the word. > { > if (root->wordEnd) words.add(word); > } > else if (*filter == '.') // Search for words with any letter > { > for(int i = 'a'; i <= 'z' ; ++i) > findWords(root->link[i], filter+1, word+i); > } > else // Search for words with the required letter > { > findWords(root->link[*filter], filter+1, word+*filter); > } > } > > On May 28, 11:36 pm, avinesh saini <[email protected]> wrote: > > Thank you Don, I was also trying in similar way. But here I'm confused > how > > you are storing the traversed words. Are you adding whole words at the > node > > on which word is ending during insertion. > > > > > > > > > > > > > > > > > > > > On Wed, May 29, 2013 at 12:36 AM, Don <[email protected]> wrote: > > > void findWords(trie *root, char *filter) > > > { > > > if (!root) return; > > > > > if (*filter == 0) // When you reach the end of the filter at the > > > end of a valid word, add the word. > > > { > > > if (root->words) words.add(root->word); > > > } > > > else if (*filter == '.') // Search for words with any letter > > > { > > > for(int i = 'a'; i <= 'z' ; ++i) > > > findWords(root->link[i], filter+1); > > > } > > > else // Search for words with the required letter > > > { > > > findWords(root->link[*filter], filter+1); > > > } > > > } > > > > > On May 28, 4:47 am, avinesh saini <[email protected]> wrote: > > > > How to search all the matching words for a filter in a trie. > > > > e.g. > > > > searching by filter "...r..m" will find all the words(of length = > 7) in > > > > trie in which 4th character is 'r' and 7th character is 'm'. > > > > > > -- > > > > * > > > > * > > > > *thanks & regards,* > > > > *Avinesh > > > > * > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To unsubscribe from this group and stop receiving emails from it, send > an > > > email to [email protected]. > > > > -- > > * > > * > > *thanks & regards,* > > *Avinesh > > * > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
