Problem Statement

Given a words array containing non-duplicate strings, return all the concatenated words that are in the words array.

A concatenated word is a string that is formed entirely of at least two shorter words (May be same) of the given array.

Examples

• Example 1:

  • Input: words = ["tree","cat","cattree","dog","catdog"]
  • Expected Output: ["cattree", "catdog"]
  • Justification: 'cattree' is formed by concatenating 'cat' and 'tree'. Similarly, 'catdog' is a combination of 'cat' and 'dog'. Both 'cattree' and 'catdog' consist entirely of shorter words found in the array.

• Example 2:

  • Input: words = ["blue","sky","bluesky","sea","sun","seasun"]
  • Expected Output: ["bluesky", "seasun"]
  • Justification: 'bluesky' combines 'blue' and 'sky', while 'seasun' is formed by 'sea' and 'sun'. Both words are made up entirely of shorter words from the list.

• Example 3:

  • Input: ["note","book","pen","notebook","penbook","notebookpenbook"]
  • Expected Output: ["notebook", "penbook", "notebookpenbook"]
  • Justification: 'notebook' is formed by concatenating 'note' and 'book'. 'penbook' combines 'pen' and 'book'. 'notebookpenbook' is an amalgamation of 'notebook' and 'penbook'.

Try it yourself

Try solving this question here: