Concatenated Words

hard trie dp string

Problem

Given a list of distinct words, return all words that are concatenations of at least two shorter words from the list.

Input["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]

Output["catsdogcats","dogcatsdog","ratcatdogcat"]

Each output word breaks into ≥ 2 other dictionary words.

words (comma-separated)

def find_all_concatenated_words(words):
    s = set(words)
    out = []
    def word_break(w):
        n = len(w)
        dp = [False]*(n + 1); dp[0] = True
        for i in range(1, n + 1):
            for j in range(i):
                if dp[j] and w[j:i] in s and w[j:i] != w:
                    dp[i] = True; break
        return dp[n]
    for w in words:
        if w and word_break(w): out.append(w)
    return out

function findAllConcatenatedWordsInADict(words) {
  const set = new Set(words);
  const out = [];
  function wb(w) {
    const n = w.length;
    const dp = new Array(n + 1).fill(false); dp[0] = true;
    for (let i = 1; i <= n; i++) {
      for (let j = 0; j < i; j++) {
        const sub = w.slice(j, i);
        if (dp[j] && set.has(sub) && sub !== w) { dp[i] = true; break; }
      }
    }
    return dp[n];
  }
  for (const w of words) if (w && wb(w)) out.push(w);
  return out;
}

class Solution {
    Set set;
    public List findAllConcatenatedWordsInADict(String[] words) {
        set = new HashSet<>(Arrays.asList(words));
        List out = new ArrayList<>();
        for (String w : words) if (!w.isEmpty() && wb(w)) out.add(w);
        return out;
    }
    boolean wb(String w) {
        int n = w.length();
        boolean[] dp = new boolean[n + 1]; dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                String sub = w.substring(j, i);
                if (dp[j] && set.contains(sub) && !sub.equals(w)) { dp[i] = true; break; }
            }
        }
        return dp[n];
    }
}

class Solution {
    unordered_set S;
    bool wb(const string& w) {
        int n = w.size();
        vector dp(n + 1, false); dp[0] = true;
        for (int i = 1; i <= n; i++)
            for (int j = 0; j < i; j++) {
                string sub = w.substr(j, i - j);
                if (dp[j] && S.count(sub) && sub != w) { dp[i] = true; break; }
            }
        return dp[n];
    }
public:
    vector findAllConcatenatedWordsInADict(vector& words) {
        S.insert(words.begin(), words.end());
        vector out;
        for (auto& w : words) if (!w.empty() && wb(w)) out.push_back(w);
        return out;
    }
};

Explanation

A word is "concatenated" if you can chop it into pieces where every piece is itself a word from the list. This is the classic word break problem run once for each word, using the whole list as the dictionary.

First we dump all words into a set for instant lookup. Then for each word w we fill a boolean array dp where dp[i] means "the first i letters of w can be split into dictionary words." We seed dp[0] = True (empty prefix is trivially fine).

For each end position i, we look back at every split point j: if dp[j] was reachable and the chunk w[j:i] is in the set, then dp[i] becomes true too. The key guard is w[j:i] != w — a word may not use itself as a piece, which forces at least two real sub-words.

Example: "catsdogcats". We can reach the end via cats + dog + cats, each in the list and none equal to the whole word, so dp[n] is true and it joins the answer. "hippopotamuses" breaks nowhere, so it does not.

Running word break for each of the N words, each costing about L², gives the overall cost.

Time: O(N · L²) Space: O(N · L)