If I try to check every way of placing words, I get 'Time limit exceeded' on test 5, and if I just first sort the words by lengths, and then try to find the first way of placing words and give it as answer, I get 'Wrong answer' on test 3. Could you please help me?

Dynamic programming

Try to create determinated finite automaton in graph realization. Use binary search to find the words in dictionary.

The Aho-Corasick algorithm will do it with linear time.

Thank you. I'll try :)

Unfortunately, I got TLE on the 8th input even if I implemented DP.

Oh I know the reason. When two or more strings map to one series of number, since any solutions are qualified, it is possible to choose only one. Also, a compartmentalization to which position(0-s.length()) the string can fit in is recommended.

Edited by author 16.03.2009 10:20

can you please give me one test case where you sort the words by length and you get wrong answer? (i used similar technique and got wrong ans for test 3 as well)