It passes for O(n* dictsize) complexity code but won't pass if you are using a hashmap (EDIT THIS IS FOR PROBLEM WORD BREAK 1)


Comment body goes here.


large values of n hashmap won’t work in O(1) time for lookup…in worst case hashmap complexity will be O(N^3) (its O(N^2 * L) ) if L = N .
while if the complexity of code is O(N*size of dict ) it will shoot up to O(N^4) since max size of dict can be N^3 . but this solution passes because in test cases size of dictionary is very small maybe around size of N making the whole complexity O(N^2) .

This is the reason why hashmap solutions are not getting passed because if you look at the testcases size n is large but dictionary size is small.

it means that hashmap solution is working in its worst case while the solution without hashmap( in which you simply iterate through the dictionary one by one and see if its present in the string A and then call recurion on remaining string ) passes .

So its my request that problem setter should increase the size of dictionary comparable to O(N^3)
so that it doesnot create to the programmers who are wondering why a hashmap solution is not passing but a solution without hashmap gives AC out of the blue .