Interesting Dyn. Pgming question

[santhoshvai]

You have an array of english words {cat, then, hen, end, dog}. Can you make out if the given sentence is a concatenation of only words from the array?

Cathen -> valid
thend -> not valid
cathenend -> valid

---

I think a trie can be used here. Like a suffix tree. What do you think? (google qn btw)

EDIT: GFG link