• Difficulty: Hard
• Patterns:
  • Queue

---

Problem Definition

Given a list of words, return a set of all sets of words that can be combined in order to form other words in the list.

---

Example

get_composite_words(["foo", "bar", "baz", "foob", "ar", "fo", "ob", "foobar"]) ->
	[ ["foo", "bar"], ["foob", "ar"], ["fo", "ob", "ar"] ]

---

Queue-Based Solution

We will use a queue to track word remainders that need to be satisfied.

def get_composite_words(words):
    valid_words = set()
    max_len = 0
    for word in words:
        valid_words.add(word)
        if max_len < len(word):
            max_len = len(word)
    q = []
    for word in words:
        if any(valid_word.startswith(word) and valid_word != word for valid_word in valid_words):
            q.append((word,))
    res = []
    while q:
        elem = q.pop()
        for word in words:
            if word not in elem:
                candidate = "".join(elem) + word
                new_elem = elem + (word,)
                if candidate in valid_words:
                    res.append(new_elem)
                if len(candidate) < max_len:
                    q.append(new_elem)
    return res

---

Queue-Based Solution Complexity

Let $n = $ len(words).

Runtime complexity should be $O(n^3)$.

Auxiliary space complexity should be $O(n)$.

---

Generative Solution

We can instead compose all words that are less than or equal to the length of the largest word and then filter out just those words that are in the original words. This solution is a lot easier to reason about and has a much simpler complexity profile.

def get_composite_words(words):
    valid_words = set()
    max_len = 0
    for word in words:
        valid_words.add(word)
        if max_len < len(word):
            max_len = len(word)
    q = []
    for word in words:
        if any(valid_word.startswith(word) and valid_word != word for valid_word in valid_words):
            q.append((word,))
    res = []
    while q:
        elem = q.pop()
        for word in words:
            if word not in elem:
                candidate = "".join(elem) + word
                new_elem = elem + (word,)
                if candidate in valid_words:
                    res.append(new_elem)
                if len(candidate) < max_len:
                    q.append(new_elem)
    return res

---

Generative Solution Complexity

Let $n = $ len(words).

Runtime complexity should be $O(n^2)$.

Auxiliary space complexity should be $O(n)$.