yashi's blog

Trie — C. Watto and Mechanism
By yashi, history, 9 years ago, In English

Hello coders,
Hope everyone's fine and doing well,

I need your help folk, I'm trying to solve this problem C. Watto and Mechanism and got stuck for a couple of days .

The problem in a nutshell : Given n strings then m queries (each query is a string) 0 <= n,m <= 3*10^5 for each query determine if the string mi exists in the set of n with at most one mismatch .

What I did : put all the n strings in a Trie then for each query traversal the trie and allow just one character to mismatch, if the query ended in a leaf then return true, else return false .

I'm not sure if this approach will pass in the TL but at least I think it's true .
Here's my code .
I'm still getting WA on test 6 and test 6 is too long to be shown, I really tried so many arbitrary test cases and my code could produce the right output for them I revised the code and the algorithm multiple times but could not find what's going wrong!

Any help would be highly appreciated,
Thanks in advance .

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The problem requires that there exists one mismatch. I believe you are returning "yes" when the query string exists in the given N strings. 

if(word[0]=='\0' && root->e) return 1;

Should be

if(word[0]=='\0' && root->e) return mismatch;
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh my bad...!!!
    How did I misread it..!!!

    It might be because I was stressed and very frustrated these two days, I tried several problems today and yesterday and couldn't solve anyone so I totally lost my confidence in my skills... :'(

    Thank you very much I do appreciate your retouch to my code .

    → Reply