Detect words formed by multiple dictionary parts
Overview
This question evaluates proficiency in string processing, selection and use of appropriate data structures and algorithms (hashing, tries), dynamic programming and memoization, and complexity analysis for large inputs and edge-case handling within the Coding & Algorithms domain.
Given an array words of up to 100,000 non-empty lowercase strings (total characters ≤ 1,000, 000), return all strings that can be formed by concatenating at least two other strings from the same array. Component strings may be reused multiple times. Describe two approaches (hash-set with dynamic programming, and trie with DFS plus memoization), analyze time and space complexity, and explain how to avoid counting a word as itself unless it is split into smaller parts. Discuss edge cases such as very short words, repeated components, and large inputs.