Return a Map of words which can be formed by using other words which exist in the same list

Viewed 442

Given a list of words return a Map of words which can be formed by using other words which exist in the same list.

 input = [“happy”, “rise”, “for”, “set”, “sunrise”, “su”, “nset”, “sunset”, “mind”, “happymind”, “n”, “rise”, “happysunrise”]

 output = {
  “happymind” : [[“happy”, “mind]],
  “sunrise” : [[“su”, “n”, “rise”], [“sun”, “rise”]],
  “sunset” : [[“sun”, “set”], [“su”, “n”, “set]],  
  “happysunrise” : [[“happy”, “sunrise”], [“happy”, “sun”, “rise”], [“happy”, “su”, “n”, 
   “rise”]]
 }
1 Answers

I have tried Making trie of these words. But couldn't reach to the solution. Then i think of another solution by making a map of count of every word in dictionary. Then For each word like "happy" find in dictionary by traversing each letter like

"happy"
"h" + "appy"
"ha" + "ppy"
"hap" + "py"
"happ" + "y"

But in this solution i am failing in those words which have a letter in between.Like

"sunrise" n is coming in between.
Related