Dubious complexity analysis in editorials

Competitive Programming
1

In editorial of this problem it says space complexity of intuition- 1 is O (1) which is not true because we do a DFS, in complexity analysis of intuition - 2, I believe both time and space complexity are wrong. Time complexity is given as O (M * N * L) , we can just say we traverse every path once and only those path which have corresponding string in our Trie (but we could visit them multiple times if the different paths correspond to same string). Space complexity is given as O (26 ^L) which is exponential where as time complexity is not (it maybe a typo of O (26 * L), which is not exact but I could let it pass)

Also problem being judged must have constraints right ?

2

Hi thanks for reporting it.
We have updated the Space Complexities!

And sorry, Interview problems have no constraints, just like a real interview problem won’t have! You would be asked to improve on your solution again and again until you achieve the best.

1 Like