Concatenated Words

🎯

Concatenated Words

hardTRIEAmazonGoogleFacebook

Imagine you have a dictionary of words and want to find which words can be formed by concatenating other words from the same dictionary. This is like checking if a complex password is made by combining simpler known words.

💡 This problem is about checking if words can be formed by joining other words. Beginners struggle because it requires efficiently searching prefixes and handling overlapping subproblems, which naive methods can't do well.

📋

Problem Statement

Given an array of strings words (without duplicates), return all the 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.

1 ≤ words.length ≤ 10^51 ≤ words[i].length ≤ 30All strings consist of lowercase English letters onlyNo duplicates in words

💡

Example

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

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

For example, "catsdogcats" can be formed by concatenating "cats", "dog", and "cats".

• Empty string in words → should not cause false positives
• Words that are prefixes of others but not concatenated → not included
• Single character words repeated → concatenated if combined
• Words that can be formed by concatenating themselves only once → not valid

⚠️

Common Mistakes

Counting the word itself as a concatenation

False positives where a word is considered concatenated by itself

✅ Temporarily disable the word in the dictionary or Trie before checking

Not memoizing recursive calls

Exponential time leading to TLE

✅ Use a memo cache keyed by substring or start index

Trying full word as prefix in recursion

Infinite recursion or incorrect results

✅ Only split word into prefix and suffix where prefix length < word length

Ignoring empty strings in input

Incorrect results or runtime errors

✅ Skip empty strings or handle them explicitly

Using substring operations inefficiently

High time complexity due to repeated substring creation

✅ Use Trie traversal or indices instead of substring slicing

🧠

Brute Force (Pure Recursion with String Matching)

💡 Starting with brute force helps understand the problem deeply by trying all possible splits, even though it's inefficient.

Intuition

Try to split each word into two parts and check if both parts are in the dictionary or can be formed by concatenation recursively.

Algorithm

1. For each word, try every possible split into prefix and suffix (excluding full word prefix).
2. Check if prefix is in the dictionary.
3. If prefix is valid, recursively check if suffix is a concatenated word or in the dictionary.
4. If any split validates the word as concatenated, add it to the result.

💡 This approach is straightforward but leads to repeated work and exponential time due to overlapping subproblems.

</>

Code

class Solution:
    def findAllConcatenatedWordsInADict(self, words):
        word_set = set(words)

        def canForm(word: str, count: int) -> bool:
            if not word:
                return count >= 2  # At least two words used
            for i in range(1, len(word)):
                prefix = word[:i]
                if prefix in word_set:
                    if canForm(word[i:], count + 1):
                        return True
            return False

        result = []
        for word in words:
            if word and canForm(word, 0):
                result.append(word)
        return result

# Example usage:
if __name__ == '__main__':
    sol = Solution()
    words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
    print(sol.findAllConcatenatedWordsInADict(words))

Line Notes

word_set = set(words)Create a set for O(1) lookups of words to quickly check prefixes

def canForm(word: str, count: int) -> bool:Recursive helper to check if word can be formed by concatenation with count tracking number of words used

if not word:Base case: if empty string reached, check if at least two words were used to ensure concatenation

for i in range(1, len(word))Try every possible prefix split except full word to avoid counting the word itself

if prefix in word_set:Check if prefix is a valid word in the dictionary

if canForm(word[i:], count + 1):Recursively check suffix with incremented count of words used

result = []Store concatenated words found in the result list

for word in words:Check each word in the list to determine if it is concatenated

import java.util.*;

public class Solution {
    private Set<String> wordSet;

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        wordSet = new HashSet<>(Arrays.asList(words));
        List<String> result = new ArrayList<>();
        for (String word : words) {
            if (!word.isEmpty() && canForm(word, 0)) {
                result.add(word);
            }
        }
        return result;
    }

    private boolean canForm(String word, int count) {
        if (word.length() == 0) {
            return count >= 2; // At least two words used
        }
        for (int i = 1; i < word.length(); i++) {
            String prefix = word.substring(0, i);
            if (wordSet.contains(prefix)) {
                if (canForm(word.substring(i), count + 1)) {
                    return true;
                }
            }
        }
        return false;
    }

    // Example usage
    public static void main(String[] args) {
        Solution sol = new Solution();
        String[] words = {"cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"};
        System.out.println(sol.findAllConcatenatedWordsInADict(words));
    }
}

Line Notes

wordSet = new HashSet<>(Arrays.asList(words));Initialize set for quick word lookup to check prefixes efficiently

for (String word : words)Iterate over each word to check if it is concatenated

if (!word.isEmpty() && canForm(word, 0))Skip empty words and check if word can be formed by concatenation starting with count 0

if (word.length() == 0)Base case: empty string means successful concatenation if at least two words used

for (int i = 1; i < word.length(); i++)Try every prefix split except full word to avoid self counting

if (wordSet.contains(prefix))Check if prefix is a valid word in the dictionary

if (canForm(word.substring(i), count + 1))Recursively check suffix with incremented count

public static void main(String[] args)Driver code to test the solution with example input

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

class Solution {
    unordered_set<string> wordSet;
public:
    bool canForm(const string& word, int count) {
        if (word.empty()) return count >= 2; // At least two words used
        for (int i = 1; i < (int)word.size(); i++) {
            string prefix = word.substr(0, i);
            if (wordSet.count(prefix)) {
                if (canForm(word.substr(i), count + 1)) return true;
            }
        }
        return false;
    }

    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        for (const string& w : words) wordSet.insert(w);
        vector<string> result;
        for (const string& w : words) {
            if (!w.empty() && canForm(w, 0)) result.push_back(w);
        }
        return result;
    }
};

int main() {
    Solution sol;
    vector<string> words = {"cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"};
    vector<string> res = sol.findAllConcatenatedWordsInADict(words);
    for (auto& w : res) cout << w << "\n";
    return 0;
}

Line Notes

unordered_set<string> wordSet;Set for O(1) word lookups to quickly check prefixes

bool canForm(const string& word, int count)Recursive function to check if word can be formed by concatenation with count tracking words used

if (word.empty()) return count >= 2;Base case: empty string means success if at least two words used

for (int i = 1; i < (int)word.size(); i++)Try all prefix splits except full word to avoid self counting

if (wordSet.count(prefix))Check if prefix is a valid word

if (canForm(word.substr(i), count + 1)) return true;Recursively check suffix with incremented count

for (const string& w : words) wordSet.insert(w);Insert all words into set for lookup

for (const string& w : words)Check each word in the list

var findAllConcatenatedWordsInADict = function(words) {
    const wordSet = new Set(words);

    function canForm(word, count) {
        if (word.length === 0) return count >= 2; // At least two words used
        for (let i = 1; i < word.length; i++) {
            const prefix = word.substring(0, i);
            if (wordSet.has(prefix)) {
                if (canForm(word.substring(i), count + 1)) return true;
            }
        }
        return false;
    }

    const result = [];
    for (const word of words) {
        if (word && canForm(word, 0)) result.push(word);
    }
    return result;
};

// Example usage
const words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"];
console.log(findAllConcatenatedWordsInADict(words));

Line Notes

const wordSet = new Set(words);Create set for O(1) lookups to quickly check prefixes

function canForm(word, count)Recursive helper to check if word can be formed by concatenation with count tracking words used

if (word.length === 0) return count >= 2;Base case: empty string means success if at least two words used

for (let i = 1; i < word.length; i++)Try every prefix split except full word to avoid self counting

if (wordSet.has(prefix))Check if prefix is a valid word

if (canForm(word.substring(i), count + 1)) return true;Recursively check suffix with incremented count

const result = []Store concatenated words found

for (const word of words)Check each word in the list

⏱

Complexity

TimeO(n * L^3) exponential in worst case due to trying all splits and recursive calls without caching

SpaceO(n * L) for recursion stack and set storage

For each word, we try all splits and recursively check suffixes, leading to exponential calls in worst case without memoization.

💡 For n=10 and max word length 10, this can already be thousands of calls, making it impractical for large inputs.

Interview Verdict: TLE / Use only to introduce the problem and intuition

This approach is too slow for large inputs but helps understand the problem and motivates optimization.

🧠

Memoization (Top-Down DFS with Caching)

💡 Memoization avoids repeated work by caching results of subproblems, making recursion feasible for larger inputs.

Intuition

Use a cache to remember if a suffix can be formed by concatenation, so we don't recompute the same substring multiple times.

Algorithm

1. Initialize a set of words for O(1) lookups.
2. Define a recursive function with memoization to check if a word can be formed by concatenation.
3. For each prefix, if it is in the set, recursively check suffix using memo cache.
4. Return true if any split validates the word; otherwise false.

💡 Memoization drastically reduces the number of recursive calls by storing intermediate results.

</>

Code

class Solution:
    def findAllConcatenatedWordsInADict(self, words):
        word_set = set(words)
        memo = {}

        def canForm(word):
            if word in memo:
                return memo[word]
            for i in range(1, len(word)):
                prefix = word[:i]
                suffix = word[i:]
                if prefix in word_set:
                    if suffix in word_set or canForm(suffix):
                        memo[word] = True
                        return True
            memo[word] = False
            return False

        result = []
        for word in words:
            if word and canForm(word):
                result.append(word)
        return result

# Example usage:
if __name__ == '__main__':
    sol = Solution()
    words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
    print(sol.findAllConcatenatedWordsInADict(words))

Line Notes

memo = {}Cache results of subproblems to avoid recomputation and speed up recursion

if word in memo:Return cached result if available to prevent repeated work

for i in range(1, len(word))Try all prefix splits except full word to avoid self counting

if prefix in word_set:Check if prefix is a valid word in the dictionary

if suffix in word_set or canForm(suffix)Check if suffix is valid or can be formed recursively

memo[word] = TrueCache positive result to reuse later

memo[word] = FalseCache negative result to avoid repeated checks

for word in words:Check each word in the list

import java.util.*;

public class Solution {
    private Set<String> wordSet;
    private Map<String, Boolean> memo;

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        wordSet = new HashSet<>(Arrays.asList(words));
        memo = new HashMap<>();
        List<String> result = new ArrayList<>();
        for (String word : words) {
            if (!word.isEmpty() && canForm(word)) {
                result.add(word);
            }
        }
        return result;
    }

    private boolean canForm(String word) {
        if (memo.containsKey(word)) return memo.get(word);
        for (int i = 1; i < word.length(); i++) {
            String prefix = word.substring(0, i);
            String suffix = word.substring(i);
            if (wordSet.contains(prefix)) {
                if (wordSet.contains(suffix) || canForm(suffix)) {
                    memo.put(word, true);
                    return true;
                }
            }
        }
        memo.put(word, false);
        return false;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        String[] words = {"cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"};
        System.out.println(sol.findAllConcatenatedWordsInADict(words));
    }
}

Line Notes

memo = new HashMap<>();Cache to store results of subproblems and avoid repeated recursion

if (memo.containsKey(word))Return cached result if present to speed up computation

for (int i = 1; i < word.length(); i++)Try all prefix splits except full word to avoid self counting

if (wordSet.contains(prefix))Check if prefix is a valid word

if (wordSet.contains(suffix) || canForm(suffix))Check suffix validity or recurse

memo.put(word, true);Cache positive result for reuse

memo.put(word, false);Cache negative result to avoid repeated checks

for (String word : words)Iterate over all words to check

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
using namespace std;

class Solution {
    unordered_set<string> wordSet;
    unordered_map<string, bool> memo;
public:
    bool canForm(const string& word) {
        if (memo.count(word)) return memo[word];
        for (int i = 1; i < (int)word.size(); i++) {
            string prefix = word.substr(0, i);
            string suffix = word.substr(i);
            if (wordSet.count(prefix)) {
                if (wordSet.count(suffix) || canForm(suffix)) {
                    memo[word] = true;
                    return true;
                }
            }
        }
        memo[word] = false;
        return false;
    }

    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        for (const string& w : words) wordSet.insert(w);
        vector<string> result;
        for (const string& w : words) {
            if (!w.empty() && canForm(w)) result.push_back(w);
        }
        return result;
    }
};

int main() {
    Solution sol;
    vector<string> words = {"cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"};
    vector<string> res = sol.findAllConcatenatedWordsInADict(words);
    for (auto& w : res) cout << w << "\n";
    return 0;
}

Line Notes

unordered_map<string, bool> memo;Cache results to avoid recomputation and speed up recursion

if (memo.count(word)) return memo[word];Return cached result if available

for (int i = 1; i < (int)word.size(); i++)Try all prefix splits except full word to avoid self counting

if (wordSet.count(prefix))Check if prefix is a valid word

if (wordSet.count(suffix) || canForm(suffix))Check suffix validity or recurse

memo[word] = true;Cache positive result

memo[word] = false;Cache negative result

for (const string& w : words)Check each word

var findAllConcatenatedWordsInADict = function(words) {
    const wordSet = new Set(words);
    const memo = new Map();

    function canForm(word) {
        if (memo.has(word)) return memo.get(word);
        for (let i = 1; i < word.length; i++) {
            const prefix = word.substring(0, i);
            const suffix = word.substring(i);
            if (wordSet.has(prefix)) {
                if (wordSet.has(suffix) || canForm(suffix)) {
                    memo.set(word, true);
                    return true;
                }
            }
        }
        memo.set(word, false);
        return false;
    }

    const result = [];
    for (const word of words) {
        if (word.length > 0 && canForm(word)) result.push(word);
    }
    return result;
};

// Example usage
const words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"];
console.log(findAllConcatenatedWordsInADict(words));

Line Notes

const memo = new Map();Cache results of subproblems to avoid repeated recursion

if (memo.has(word)) return memo.get(word);Return cached result if present

for (let i = 1; i < word.length; i++)Try all prefix splits except full word to avoid self counting

if (wordSet.has(prefix))Check if prefix is a valid word

if (wordSet.has(suffix) || canForm(suffix))Check suffix validity or recurse

memo.set(word, true);Cache positive result

memo.set(word, false);Cache negative result

for (const word of words)Check each word

⏱

Complexity

TimeO(n * L^3) amortized due to memoization reducing repeated calls

SpaceO(n * L) for memo and set storage

Memoization prunes repeated recursive calls, making it much faster than brute force but still costly for very large inputs.

💡 For n=10^4 and max length 30, memoization can handle the problem efficiently compared to brute force.

Interview Verdict: Accepted / Practical for large inputs

Memoization is a common and effective optimization that interviewers expect after brute force.

🧠

Trie + DFS with Memoization

💡 Using a Trie to store words allows prefix checks in O(L) time, improving efficiency over set lookups and enabling faster pruning.

Intuition

Build a Trie of all words, then for each word, use DFS to check if it can be formed by concatenating other words by traversing the Trie and memoizing results.

Algorithm

1. Build a Trie containing all words.
2. For each word, use DFS starting from index 0 to check if it can be formed by concatenation.
3. At each DFS step, traverse the Trie nodes for prefixes; when a word end is found, recursively check the suffix.
4. Use memoization to cache results for each start index to avoid repeated work.

💡 Trie traversal reduces prefix checks from O(L) substring lookups to O(1) per character, speeding up the search.

</>

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Solution:
    def findAllConcatenatedWordsInADict(self, words):
        root = TrieNode()

        def insert(word):
            node = root
            for ch in word:
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            node.is_word = True

        for word in words:
            if word:
                insert(word)

        memo = {}

        def dfs(word, start):
            if start == len(word):
                return True
            if start in memo:
                return memo[start]
            node = root
            for i in range(start, len(word)):
                ch = word[i]
                if ch not in node.children:
                    break
                node = node.children[ch]
                if node.is_word:
                    if dfs(word, i + 1):
                        memo[start] = True
                        return True
            memo[start] = False
            return False

        result = []
        for word in words:
            if not word:
                continue
            memo.clear()
            # To avoid counting the word itself as concatenation, temporarily remove it
            node = root
            for ch in word:
                node = node.children[ch]
            node.is_word = False
            if dfs(word, 0):
                result.append(word)
            node.is_word = True
        return result

# Example usage:
if __name__ == '__main__':
    sol = Solution()
    words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
    print(sol.findAllConcatenatedWordsInADict(words))

Line Notes

class TrieNode:Define Trie node with children dictionary and is_word flag to mark word ends

def insert(word):Insert words into Trie for efficient prefix lookup

memo = {}Cache DFS results for start indices to avoid repeated work

def dfs(word, start):DFS to check if word can be formed by concatenation starting at index start

if start == len(word):Base case: reached end means successful concatenation

if start in memo:Return cached DFS result if available

for i in range(start, len(word))Traverse Trie nodes for prefixes starting at start index

if node.is_word:If prefix is a word, recursively check suffix starting at next index

node.is_word = FalseTemporarily disable current word to avoid counting itself as concatenation

node.is_word = TrueRestore word flag after DFS check

import java.util.*;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isWord = false;
}

public class Solution {
    TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
        }
        node.isWord = true;
    }

    public boolean dfs(String word, int start, Map<Integer, Boolean> memo) {
        if (start == word.length()) return true;
        if (memo.containsKey(start)) return memo.get(start);
        TrieNode node = root;
        for (int i = start; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (!node.children.containsKey(ch)) break;
            node = node.children.get(ch);
            if (node.isWord) {
                if (dfs(word, i + 1, memo)) {
                    memo.put(start, true);
                    return true;
                }
            }
        }
        memo.put(start, false);
        return false;
    }

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        for (String word : words) {
            if (!word.isEmpty()) insert(word);
        }
        List<String> result = new ArrayList<>();
        for (String word : words) {
            if (word.isEmpty()) continue;
            TrieNode node = root;
            for (char ch : word.toCharArray()) {
                node = node.children.get(ch);
            }
            node.isWord = false; // temporarily disable
            Map<Integer, Boolean> memo = new HashMap<>();
            if (dfs(word, 0, memo)) {
                result.add(word);
            }
            node.isWord = true; // restore
        }
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        String[] words = {"cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"};
        System.out.println(sol.findAllConcatenatedWordsInADict(words));
    }
}

Line Notes

class TrieNode {Trie node with children map and isWord flag to mark word ends

public void insert(String word)Insert words into Trie for efficient prefix lookup

Map<Integer, Boolean> memoMemo cache for DFS start indices to avoid repeated work

if (start == word.length()) return true;Base case: full word matched means successful concatenation

for (int i = start; i < word.length(); i++)Traverse Trie nodes for prefixes starting at start index

if (node.isWord)If prefix is a word, recurse on suffix starting at next index

node.isWord = false;Temporarily disable current word to avoid self counting

node.isWord = true;Restore word flag after DFS

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isWord = false;
};

class Solution {
    TrieNode* root = new TrieNode();

    void insert(const string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch))
                node->children[ch] = new TrieNode();
            node = node->children[ch];
        }
        node->isWord = true;
    }

    bool dfs(const string& word, int start, unordered_map<int, bool>& memo) {
        if (start == (int)word.size()) return true;
        if (memo.count(start)) return memo[start];
        TrieNode* node = root;
        for (int i = start; i < (int)word.size(); i++) {
            char ch = word[i];
            if (!node->children.count(ch)) break;
            node = node->children[ch];
            if (node->isWord) {
                if (dfs(word, i + 1, memo)) {
                    memo[start] = true;
                    return true;
                }
            }
        }
        memo[start] = false;
        return false;
    }

public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        for (const string& w : words) {
            if (!w.empty()) insert(w);
        }
        vector<string> result;
        for (const string& w : words) {
            if (w.empty()) continue;
            TrieNode* node = root;
            for (char ch : w) {
                node = node->children[ch];
            }
            node->isWord = false; // temporarily disable
            unordered_map<int, bool> memo;
            if (dfs(w, 0, memo)) result.push_back(w);
            node->isWord = true; // restore
        }
        return result;
    }
};

int main() {
    Solution sol;
    vector<string> words = {"cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"};
    vector<string> res = sol.findAllConcatenatedWordsInADict(words);
    for (auto& w : res) cout << w << "\n";
    return 0;
}

Line Notes

struct TrieNode {Trie node with children map and isWord flag to mark word ends

void insert(const string& word)Insert words into Trie for efficient prefix lookup

unordered_map<int, bool>& memoMemo cache for DFS start indices to avoid repeated work

if (start == (int)word.size()) return true;Base case: full word matched means successful concatenation

for (int i = start; i < (int)word.size(); i++)Traverse Trie nodes for prefixes starting at start index

if (node->isWord)If prefix is a word, recurse on suffix starting at next index

node->isWord = false;Temporarily disable current word to avoid self counting

node->isWord = true;Restore word flag after DFS

class TrieNode {
    constructor() {
        this.children = new Map();
        this.isWord = false;
    }
}

var findAllConcatenatedWordsInADict = function(words) {
    const root = new TrieNode();

    function insert(word) {
        let node = root;
        for (const ch of word) {
            if (!node.children.has(ch)) {
                node.children.set(ch, new TrieNode());
            }
            node = node.children.get(ch);
        }
        node.isWord = true;
    }

    function dfs(word, start, memo) {
        if (start === word.length) return true;
        if (memo.has(start)) return memo.get(start);
        let node = root;
        for (let i = start; i < word.length; i++) {
            const ch = word[i];
            if (!node.children.has(ch)) break;
            node = node.children.get(ch);
            if (node.isWord) {
                if (dfs(word, i + 1, memo)) {
                    memo.set(start, true);
                    return true;
                }
            }
        }
        memo.set(start, false);
        return false;
    }

    for (const word of words) {
        if (word) insert(word);
    }

    const result = [];
    for (const word of words) {
        if (!word) continue;
        let node = root;
        for (const ch of word) {
            node = node.children.get(ch);
        }
        node.isWord = false; // temporarily disable
        const memo = new Map();
        if (dfs(word, 0, memo)) result.push(word);
        node.isWord = true; // restore
    }
    return result;
};

// Example usage
const words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"];
console.log(findAllConcatenatedWordsInADict(words));

Line Notes

class TrieNode {Trie node with children map and isWord flag to mark word ends

function insert(word)Insert words into Trie for efficient prefix lookup

function dfs(word, start, memo)DFS with memo to check if word can be formed by concatenation starting at index start

if (start === word.length) return true;Base case: full word matched means successful concatenation

for (let i = start; i < word.length; i++)Traverse Trie nodes for prefixes starting at start index

if (node.isWord)If prefix is a word, recurse on suffix starting at next index

node.isWord = false;Temporarily disable current word to avoid self counting

node.isWord = true;Restore word flag after DFS

⏱

Complexity

TimeO(n * L^2) where n is number of words and L is max word length due to Trie traversal and memoization

SpaceO(n * L) for Trie nodes and memoization

Trie reduces prefix checks to O(L) per character, and memoization avoids repeated suffix checks, improving over set-based memoization.

💡 For max word length 30, this approach is efficient and scalable for large dictionaries.

Interview Verdict: Accepted / Optimal for interview coding

This approach shows mastery of Trie and DFS with memoization, a strong interview solution.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the Trie + DFS + memoization approach is usually best after explaining brute force and memoization.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n * L^3) exponential	O(n * L) recursion stack	Yes (deep recursion)	No	Mention only - never code
2. Memoization	O(n * L^3) amortized	O(n * L) memo and recursion	Possible but reduced	No	Good to code if Trie is unfamiliar
3. Trie + DFS + Memoization	O(n * L^2)	O(n * L) Trie + memo	Low	Yes (with minor modification)	Optimal approach to code in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem constraints and definitions (e.g., what counts as concatenated).Step 2: Present brute force recursion to show understanding of problem structure.Step 3: Introduce memoization to optimize repeated subproblems.Step 4: Discuss Trie usage to speed up prefix checks and further optimize.Step 5: Code the Trie + DFS + memoization approach carefully.Step 6: Test with edge cases and explain complexity.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 15min → Test & Optimize: 7min. Total ~30min

What the Interviewer Tests

Interviewer tests your ability to identify overlapping subproblems, optimize recursion with memoization, and use advanced data structures like Trie for efficient prefix queries.

Common Follow-ups

• How would you handle very large input with millions of words? → Use iterative DP or advanced Trie compression.
• Can you modify to return the actual concatenation sequence? → Store path info during DFS.

💡 Follow-ups test your ability to scale solutions and extend them beyond just yes/no answers.

🔍

Pattern Recognition

When to Use

1) Problem involves checking if words can be formed by concatenating others; 2) Requires efficient prefix checks; 3) Overlapping subproblems exist; 4) Trie or DP can optimize prefix queries.

Signature Phrases

'concatenated word''formed entirely by at least two shorter words'

NOT This Pattern When

Problems that only require substring search without concatenation or DP, e.g., simple substring matching.

Similar Problems

Word Break - similar substring segmentation problemWord Squares - uses Trie for prefix searchPalindrome Pairs - uses Trie for efficient word matching

Practice

1. Given the following code snippet for MapSum, after inserting keys "apple" with value 3 and "app" with value 2, what is the value of node.sum at the trie node corresponding to 'p' (the second character) after the second insert?

easy

A. 3

B. 5

C. 2

D. 0

Solution

1. Step 1: Trace insert of "apple" with value 3

   Delta = 3 - 0 = 3. Root.sum += 3 -> 3. For each character 'a','p','p','l','e', node.sum += 3. After first insert, node at second 'p' has sum 3.

2. Step 2: Trace insert of "app" with value 2

   Delta = 2 - 0 = 2. Root.sum += 2 -> 5. For 'a','p','p', node.sum += 2. Node at second 'p' sum was 3, now 3 + 2 = 5.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum at second 'p' after both inserts is 5 [OK]

Hint: Sum accumulates delta on each insert per prefix node [OK]

Common Mistakes:

• Forgetting to add delta on second insert
• Confusing first and second 'p' nodes
• Using old value instead of delta

2. Consider the following Python code implementing a bit trie for maximum XOR queries. Given nums = [1, 2] inserted into the trie, what is the value of max_xor after calling max_xor(3)?

easy

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Trace insertion of nums 1 and 2

   Bits of 1 and 2 inserted from MSB to LSB into trie.

2. Step 2: Trace max_xor(3)

   For each bit of 3, try toggled bit in trie to maximize XOR. At highest differing bit, toggled bit exists, setting max_xor bits accordingly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   3 XOR 0 = 3, 3 XOR 1 = 2, 3 XOR 2 = 1; max is 3 [OK]

Hint: XOR with 3 and 0,1,2 yields max 3 [OK]

Common Mistakes:

• Confusing bit order in trie traversal
• Off-by-one in bit indexing
• Returning wrong max_xor value

3. What is the time complexity of the optimal Word Break solution that uses iterative DP combined with a reversed trie for prefix checks, where n is the length of the string and m is the maximum length of words in the dictionary?

medium

A. O(n * log m) due to binary search in trie children

B. O(n^2) because of nested loops over the string

C. O(n * m) because for each position, trie traversal is bounded by max word length

D. O(n * m^2) because each trie traversal can take up to m steps and each step checks children

Solution

1. Step 1: Identify loops and trie traversal cost

   Outer loop runs n times. Inner loop traverses backwards up to m characters (max word length). Trie traversal per character is O(1) on average due to hashmap children.

2. Step 2: Combine to get total complexity

   Total time is O(n * m). Nested loops do not run n^2 because inner loop breaks early when no trie child exists.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Trie traversal bounded by max word length m [OK]

Hint: Trie traversal limits inner loop to max word length [OK]

Common Mistakes:

• Assuming inner loop always runs n times
• Confusing trie traversal cost with binary search
• Ignoring early breaks in inner loop

4. Suppose you want to extend the Trie to support deletion of words. Which of the following approaches correctly handles deletion without breaking prefix searches for other words?

hard

A. Remove the isEnd flag at the last node of the word and delete nodes bottom-up only if they have no children and isEnd is false

B. Delete all nodes corresponding to the word immediately, regardless of children

C. Set isEnd to false at the last node but never delete any nodes

D. Rebuild the entire trie after each deletion to remove unused nodes

Solution

1. Step 1: Understand deletion impact

   Removing isEnd flag marks word as deleted. Nodes can be deleted only if they are not prefixes of other words.

2. Step 2: Delete nodes bottom-up conditionally

   Delete nodes only if they have no children and isEnd is false to avoid breaking other words.

3. Step 3: Avoid unsafe deletions

   Deleting nodes immediately or rebuilding trie is inefficient or breaks other words.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Conditional bottom-up deletion preserves trie correctness [OK]

Hint: Delete nodes only if no children and isEnd is false [OK]

Common Mistakes:

• Deleting nodes without checking children breaks other words

5. Suppose the problem changes: you want to find the maximum XOR of two numbers in an array, but now numbers can be negative 32-bit integers. Which modification to the bitwise trie approach is necessary to handle negative numbers correctly?

hard

A. Use two's complement 32-bit representation and treat bits as unsigned during trie insertion and traversal

B. Ignore sign bit and only build trie from absolute values of numbers

C. Use 64-bit representation to store numbers in trie to avoid sign issues

D. Preprocess numbers by adding a large constant to make all numbers positive before building trie

Solution

1. Step 1: Understand representation of negative numbers

   Negative integers in 32-bit are stored in two's complement form, which can be treated as unsigned bit patterns for trie operations.

2. Step 2: Modify trie insertion and traversal

   Insert and traverse bits as unsigned 32-bit integers, including the sign bit, to correctly handle negative numbers.

3. Step 3: Avoid incorrect approaches

   Using 64-bit or adding constants changes problem semantics; ignoring sign bit loses information.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Two's complement allows uniform bitwise trie handling of negative numbers [OK]

Hint: Two's complement bits can be treated as unsigned [OK]

Common Mistakes:

• Ignoring sign bit or converting to absolute values