938. Built From Others
A word-chain game accepts a word if it can be spelled by gluing together two or more words that appear in the same dictionary words. The pieces must be non-empty dictionary words, any piece may be used several times, and a word may not be used as its own single piece.
Return every dictionary word that can be built this way, each listed once, sorted in ascending lexicographic order. Empty strings in the input are ignored and duplicates in the input count as one word. If no word qualifies, return an empty list. The dictionary can be large, so look pieces up with a trie or a hash set and test every word with dynamic programming instead of trying all splittings.
Example 1
- Input:
- words = ["ab","cd","abcd","cdab","xyz","abcdxyz"]
- Output:
- ["abcd","abcdxyz","cdab"]
- Explanation:
abcd= ab+cd,cdab= cd+ab andabcdxyz= ab+cd+xyz; the other three words are not built from shorter list words.
Example 2
- Input:
- words = ["tt","ttt","tttttt","t"]
- Output:
- ["tt","ttt","tttttt"]
- Explanation:
Parts may repeat: tt = t+t, ttt = t+t+t and tttttt = ttt+ttt, so all three longer words qualify while t itself does not.
Example 3
- Input:
- words = ["pa","pam","mapa","ma","pama"]
- Output:
- ["mapa","pama"]
- Explanation:
mapa= ma+pa andpama= pa+ma are built;pamcannot be split into listed words.
Constraints
1 ≤ words.length ≤ 8000
0 ≤ words[i].length ≤ 30
Words consist of lowercase English letters.
How this problem is judged
- Answers
- The outer list may be in any order. Everything inside each item must match exactly.
- Time per case
- Python 1,920 msC++ 480 msJava 960 msJavaScript 960 msTypeScript 960 ms
Expected complexity
- Time
- O(total length * L)
- Space
- O(total length)