@Rahul, The problem is to get all the words matching to a given filter
like *"...n..p" *from already built trie.
@Don, I'm storing words at the ending node, now I'm trying to modify this
function so that it returns only one random word from all words matching
that filter with equal probability for each word, I'm trying like this
char* randomWord(trie *root, char *k)
{
int m;
if(!root || flag) return;
if(*k == '\0') {
if(root->word) {
strcpy(mWord,root->word); // storing the random word
in mWord.
flag = 1;
}
return;
}
else if(*k == '.') {
for(m=0;m<26;m++) {
if(root->children[mark[m]]){ //
where mark[26] is an array containing numbers [0,1,2,.....,25] on random
indices.
randomWord(root->children[mark[m]],k+1);
}
}
randomize(); //
randomize function shuffles mark[].
}
else
randomWord(root->children[*k-'a'],k+1);
}
But this is not giving words with equal probability. It is returning words
more frequently which are having consecutive same letters.
On Thu, May 30, 2013 at 2:34 AM, rahul sharma <rahul23111...@gmail.com>wrote:
> 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 <dondod...@gmail.com> 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 <avinesh.sa...@gmail.com> 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 <dondod...@gmail.com> 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 <avinesh.sa...@gmail.com> 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 algogeeks+unsubscr...@googlegroups.com.
>> >
>> > --
>> > *
>> > *
>> > *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 algogeeks+unsubscr...@googlegroups.com.
>>
>>
>>
> --
> 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 algogeeks+unsubscr...@googlegroups.com.
>
>
>
--
*
*
*regards,*
*Avinesh Kumar
National Institute of Technology, Calicut.*
*Kerala- 673601*
*+91 7849080702*
*http://www.facebook.com/avinesh.saini*
--
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 algogeeks+unsubscr...@googlegroups.com.
