Why not use map<string, int> instead of implementing a trie? I understand the space requirement will be more, but it works for the above constraints (also works for most questions related to string queries). Is there any other reason why map<string, int> is not generally considered?
Should there be test cases which only pass for actual tries and not map<string, int>? That forces the user to learn/understand how to implement them. Just my thoughts on this.
Can you please post the test cases file for this particular problem so that i can know where specifically my program / logic went wrong in the bruteforce method .
@arnaagyeya: You can compare your solution with mine. I find your code quite unreadable to find the actual mistake. I’m sure you can understand your mistake after looking at my code. I just read about trie and implemented it so it may have some bugs but the solution worked for this problem.
@decagon: Thanks for the answer. I could not get where I was wrong as mine is online implementation but your implementation was very efficient. A very nice offline approach for this problem.
Is it necessary to store the entire vector of the indices of the strings at every node? Can’t we just keep the minimum index of the string at each node along that path and then the actual index of the string at it’s leaf node. Would be much more space efficient.
I used an entirely different approach, working in C#.
As each string is no more than 10 characters, each one of 26 lower case letters, each entire string can be encoded into a ‘long’, with 5 bits per letter. Comparisons like ‘CompareTo’ are then fast.
Define a class StringIndex, consisting of an encoded string and its index in the array.
Build a sorted list of StringIndex, sorted by the integer encoded string.
For each query, find its place in the sorted list by a binary search.
From there search forwards until an index within range, and set the common prefix with that string.
Then search backwards. Check whether the first one with an index in range has a longer common prefix. Search backwards until there is a shorter common prefix.
When no common prefix is found, set to the first string in the list with an index in range.
As the number being searched may be much less than the number of strings supplied, extract a series of shorter lists before starting any queries, and then choose the appropriate list to search for each query.
Using same approach as editorialist,still getting wa. eFFVqJ - Online C++0x Compiler & Debugging Tool - Ideone.com Here I am using unordered_map in trie to reduce unnecessary space but I have tried it directly also still getting wa. I am adding string no. to vector of strings at that position only if string having greater index than the last element in vector is lexicographically smaller than it
Can someone please explain the use of the member “leaf_id” in the “trie node” in editorialist’s solution
(I know it may be a lame question, but a beginner here)
Yes, it will consume less memory but in big O notation it will be same. Just wanted to explain through the example that it will still be same and such modified trie is helpful in general. Actually using it we can solve the problem for general range [l, r] instead of [1, r] but with additional O(\log{n}) factor.