Katkat
Back

Find Words Containing Other Words

MetaMachine Learning Engineer · Onsite
HardMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to efficiently identify all words in a list that contain at least one other word from the same list as a substring, utilizing optimized string processing or data structures like Tries.

Problem Statement

Given a list of unique strings words, return a list containing all words that are formed by concatenating or embedding other strings present in the input list. A word is considered "composed" if it contains at least one other string from the list as a substring (excluding the word itself).

Function Signature

def find_composed_words(words: List[str]) -> List[str]:

Constraints

  • 1 <= len(words) <= 10^4
  • 1 <= len(words[i]) <= 100
  • The total number of characters across all strings will not exceed 10^6.

Examples

Example 1: Input: words = ["cat", "dog", "catdog", "bird", "dogbird"] Output: ["catdog", "dogbird"] Explanation: "catdog" contains "cat" and "dog". "dogbird" contains "dog" and "bird".

Example 2: Input: words = ["a", "b", "ab", "abc"] Output: ["ab", "abc"] Explanation: "ab" contains "a" and "b". "abc" contains "a", "b", and "ab".

Edge Cases

  • Empty input list or a list with a single word.
  • Strings that are identical or subsets of others.
  • No words contain any other words.

Hints

Hint 1

A brute-force approach would involve checking every word against every other word, which results in O(N^2 * M) complexity where N is the number of words and M is the average length.

Hint 2

Consider sorting the list by string length first, as a word can only contain another word that is shorter than or equal to itself in length.

Hint 3

Using a Trie or a Suffix Tree to index all strings can help speed up the searching process compared to standard substring matching functions.

Follow-up questions

  • How would your solution change if you needed to identify words formed by the concatenation of exactly two other words from the list?
  • If the input list is extremely large (e.g., millions of words), what distributed approach would you take to process this?
  • How does the time complexity change if you use a Suffix Automaton instead of a Trie to perform the lookups?