Concatenated Words

How it works

For each word, we use a DP array where dp[i] indicates whether the substring from index 0 to i can be formed by concatenating words from the set. We build this array iteratively by checking all possible split points.

Steps

1. Build a hash set from all words.
2. For each word, create a boolean DP array of size m+1 with dp[0] = true.
3. For each position i from 1 to m, check all previous positions j. If dp[j] is true and the substring from j to i exists in the set, set dp[i] = true.
4. Skip the case where j = 0 and i = m to ensure the word is not just itself.
5. If dp[m] is true, the word is concatenated; add it to results.

Complexity

• Time complexity: O(n * m ^ 3)
• Space complexity: O(n * m)

Where n is the size of the string array words and m is the length of the longest word in the array.

Things to watch for

Counting a Word as Its Own Concatenation

A concatenated word must be formed by at least two other words. If you check whether the entire word exists in the set without excluding it, every word would trivially match itself.

Not Requiring Multiple Words

The problem requires concatenation of two or more words. Checking only that the word can be split into valid parts without ensuring at least two parts will incorrectly include single words that exist in the dictionary.

Missing Memoization Leading to TLE

Without memoization, the same suffix may be checked exponentially many times. For long words with many valid prefixes, this causes timeout.

Incorrect Substring Indices

Off-by-one errors when splitting the word into prefix and suffix are common. The prefix should be word[0:i] and suffix should be word[i:], where i ranges from 1 to len(word)-1.

Forgetting Empty String Edge Case

If the word list contains an empty string, it could match infinitely. Most solutions implicitly handle this since the loop starts at i=1, but explicitly filtering empty strings from the word set is safer.

from typing import List

class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        wordSet = set(words)
        res = []

        for word in words:
            m = len(word)

            dp = [False] * (m + 1)
            dp[0] = True

            for i in range(1, m + 1):
                for j in range(i):
                    if j == 0 and i == m:
                        continue
                    if dp[j] and word[j:i] in wordSet:
                        dp[i] = True
                        break

            if dp[m]:
                res.append(word)

        return res

class Solution {
public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        unordered_set<string> wordSet(words.begin(), words.end());
        vector<string> res;

        for (string& word : words) {
            int m = word.length();
            vector<bool> dp(m + 1, false);
            dp[0] = true;

            for (int i = 1; i <= m; i++) {
                for (int j = 0; j < i; j++) {
                    if (j == 0 && i == m) continue;
                    if (dp[j] && wordSet.count(word.substr(j, i - j))) {
                        dp[i] = true;
                        break;
                    }
                }
            }

            if (dp[m]) {
                res.push_back(word);
            }
        }
        return res;
    }
};