Find all concatenated words in a given list of words

Question

This is a Leetcode problem -

Given a list of words (without duplicates), write a program that returns all concatenated words in the given list of words.

A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.

Note -

• The number of elements of the given array will not exceed 10,000.
• The length sum of elements in the given array will not exceed 600,000.
• All the input string will only include lower case letters.
• The returned order of elements does not matter.

Here is my solution to this challenge (DFS solution) -

def find_all_concatenated_words_in_a_dict(words):
    """
    :type words: List[str]
    :rtype: List[str]
    """
    words = set(words)
    output = []
    for w in words:

        if not w:
            continue

        stack = [0]
        seen = {0}
        word_len = len(w)

        while stack:
            i = stack.pop()
            if i == word_len or (i > 0 and w[i:] in words):
                output.append(w)
                break
            for x in range(word_len - i + 1):
                if w[i: i + x] in words and i + x not in seen and x != word_len:
                    stack.append(i + x)
                    seen.add(i + x)
    return output

Here is an example output -

#print(find_all_concatenated_words_in_a_dict(["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"]))

>>> ['catsdogcats', 'ratcatdogcat', 'dogcatsdog']

Explanation -

"catsdogcats" can be concatenated by "cats", "dog" and "cats";

"dogcatsdog" can be concatenated by "dog", "cats" and "dog";

"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".

Here is the time taken for this output -

%timeit find_all_concatenated_words_in_a_dict(["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"])
41.1 µs ± 2.93 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

So, I would like to know whether I could make this program shorter and more efficient.

Answer 1

I took me a while to understand your code since I didn't know from the beginning what each variable really meant:

• i is probably an int, maybe an index
• x is probably a number (maybe even a float), or something unknown, or a placeholder
• seen is a set of something, and this something could really be anything
• stack will only be used by calling append and pop, but what does it contain? ints, strings, complex objects? The name stack by itself doesn't give any clue.
• w could also be spelled word, but that one is already the best of the variable names

Therefore, to really understand what each variable stands for, I had to run your code using only pen and paper, which was a good exercise since I really don't do that often.

By doing that I noticed:

• the only purpose of the if not w: continue is to prevent the empty word from being output
• the only purpose of the w[i:] in words is to speed up the implementation; it is not necessary for the pure algorithm
• the expression i + x appears several times. I wondered whether the Python runtime would be able to apply common subexpression elimination to it, or whether it would make the program faster if that expression were saved into a separate variable
• I wanted to replace the x != word_len with the simpler i != 0, but I quickly noticed that this would break the whole algorithm
• using a stack is great because the larger string indices are pushed at the end, which means they are popped and checked first, which speeds up the program. At least in the catsdogcats case
• the range should not start at 0, but at 1, since for the empty word, seen[i + x] is always True
• the code is really efficient

After finishing the manual analysis, each and every little expression made sense. I didn't discover anything superfluous. Therefore: nice work. You should make the variable names a little more suggestive though.

• i could be left
• i + x could be right
• x could be subword_len
• stack could be indices_to_test
• seen could be seen_indices

One idea I had during the analysis was that the code might become easier to understand if you used a nested function:

def find_all_concatenated_words_in_a_dict(words: List[str]) -> List[str]:
    words = set(words)

    def is_concatenated(word: str) -> bool:
        ...
        return True

    return [word for word in words if word and is_concatenated(word)]

After executing your algorithm using pen and paper, I thought that another implementation might be even more efficient, and maybe lead to shorter code. My idea was:

def is_concatenated(word: str) -> bool:
    word_breaks = [True] + [False] * len(word)

    for start in range(len(word_breaks)):
        if word_breaks[start]:
            for sub_len in range(1, len(word_breaks) - start):
                if sub_len != len(word) and word[start:start + sub_len] in words:
                    word_breaks[start+sub_len] = True

    return word_breaks[-1]

This code also starts at the beginning of the long word and marks all reachable word breaks. It uses fewer variables though.

The code can be further optimized:

• for the sub_word length, only iterate over the lengths that actually appear in the word set
• return early as soon as word_breaks[-1] becomes True

But even with these optimizations, the time complexity stays at \$\mathcal O({\text{len}(\textit{word})}^3)\$, which is quite much when \$\text{len}(\textit{word})\$ can be up to 10_000. Space complexity is \$\mathcal O(\text{len}(\textit{word}))\$, and the initial part of the word_breaks[:start] list could be thrown away early.

The \$n^3\$ is because of the 2 nested for loops, and deeply nested in these loops is a string comparison of the subword, which also depends on \$\text{len}(\textit{word})\$.

I'd rather have an \$\mathcal O(n^2)\$ or even \$\mathcal O(n)\$ algorithm though. I just don't know whether one exists.