1254 - Top 10

[sith]

Hi

I am using prefix tree to solve this task, but got TLE,
(I am using java)

Is it not enough fast?

Code: Select all

AC

[brianfry713]

My C++ code is AC in 1.7 sec. I first sort the dictionary in this order:
The words with shorter length come first, if they have equal length then
The lexicographically smaller words come first, otherwise
The words with smaller label come first.

Then for each query iterate through the dictionary until you have up to the top 10. I use std::string::find to see if the word contains the substring.

[sith]

I've got AC.

But I think that this approach is not optimal. We make a lot of substring operations.
Suffix tree would be better, but my first implementation has O(n^2) to init the tree, I believe because of that I've got TLE

[flashion]

Can I have some tests, please?

[brianfry713]

http://www.udebug.com/UVa/1254
Click "Random Input", "Go!".