How to solve this problem using trie ?
Its easy. There is a classical version of this problem called Word Break, easily found online. You simply have to use it, straightforward. Say, the algos given on geeksforgeeks are good for the easy version of this problem, but not for this hard version. For that, you need a more sophisticated Word Break algo. Just use it simply. Instant AC!