Concatenated Words solution and explanation
9 more videos on this problem
Concatenated Words - Leetcode 472 - PythonNeetCodeIO · 12:00 · 26K views
Concatenated Words | Simple Story | META | Leetcode 472codestorywithMIK · 23:17 · 18K views
Concatenated Words | LeetCode 472Pepcoding · 1:07:46 · 6K views
Concatenated Words | LeetCode problem 472Technosage · 11:26 · 6K views
Leetcode 472. Concatenated Words Solution ExplainedInterviewDose · 10:57 · 6K views
leetcode 472 Concatenated WordsCodebix · 11:36 · 5K views
LeetCode 472. Concatenated WordsHappy Coding · 22:37 · 2K views
Leetcode 472. Concatenated Words | Dynamic ProgrammingNeedCode⚡ · 6:15 · 2K views
472. Concatenated Words (Leetcode Hard)Programming Live with Larry · 55:57 · 1K views
472. Concatenated Words | LeetCodeDeep Tech · 11:17 · 1K views
The problem
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 (not necessarily distinct) in the given array.
Example 1:
Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"] Output: ["catsdogcats","dogcatsdog","ratcatdogcat"] 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".
Example 2:
Input: words = ["cat","dog","catdog"] Output: ["catdog"]
Constraints:
1 <= words.length <= 1041 <= words[i].length <= 30words[i]consists of only lowercase English letters.- All the strings of
wordsare unique. 1 <= sum(words[i].length) <= 105
Approach overview
Problem Overview: You are given a dictionary of unique words. The task is to return all words that can be formed by concatenating at least two shorter words from the same dictionary. Each word can reuse other dictionary entries, but the concatenated word itself cannot be counted as its own component.
Approach 1: Trie + Depth-First Search (O(N * L^2) time, O(N * L) space)
This approach stores all words in a trie and checks each word using depth-first search. Starting from index 0, traverse the trie character by character. Whenever you reach a terminal node (a complete word), recursively attempt to match the remaining suffix. If the DFS reaches the end of the string after using at least two words, the word is valid. The trie allows fast prefix checks while DFS explores possible split points. This method works well when many words share prefixes because trie traversal avoids repeated substring lookups.
The key idea is treating the word as a sequence of smaller dictionary prefixes. The trie ensures prefix lookups happen in O(L) time, while DFS handles branching splits. Memoization on indices can further reduce repeated work when the same suffix is evaluated multiple times.
Approach 2: Dynamic Programming (O(N * L^2) time, O(L) space per word)
This solution treats the problem like a classic word break variant using dynamic programming. Sort words by length so shorter words are processed first. For each word, build a boolean DP array where dp[i] indicates whether the prefix ending at index i can be formed using previously processed words. Iterate over all split points j < i and check if dp[j] is true and the substring word[j:i] exists in a hash set.
If the final index becomes reachable and the word uses at least two components, it is a concatenated word. After evaluation, add the word to the dictionary so longer words can reuse it. Sorting ensures each word only depends on smaller ones, preventing self-construction. This approach is straightforward and relies heavily on efficient substring membership checks.
Recommended for interviews: The dynamic programming approach is usually expected because it mirrors the classic Word Break pattern and is easier to reason about during an interview. Implementing trie + DFS demonstrates stronger understanding of prefix structures and search strategies, which can be useful when the dictionary has heavy prefix overlap. Showing the DP baseline first and then discussing trie optimization demonstrates strong problem-solving depth.
Approach 1: Trie and Depth-First Search (DFS)
This approach involves using a Trie data structure to store all words. We then perform a DFS to check if a word can be formed using other words in the trie. The main advantage of using a Trie is that it provides an efficient way to store and look up words simply by traversing nodes based on each character of the word.
We will mark nodes in the Trie that represent the end of a word and during DFS checks if the current segment of the word is in the Trie.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Solution:
def insert(self, root, word):
node = root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def dfs(self, root, word, start, count):
if start == len(word):
return count >= 2
node = root
for i in range(start, len(word)):
char = word[i]
if char not in node.children:
return False
node = node.children[char]
if node.is_end_of_word:
if self.dfs(root, word, i + 1, count + 1):
return True
return False
def findAllConcatenatedWordsInADict(self, words):
root = TrieNode()
for word in words:
if word:
self.insert(root, word)
result = []
for word in words:
if self.dfs(root, word, 0, 0):
result.append(word)
return result
# Usage example
if __name__ == "__main__":
sol = Solution()
words = ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"]
concatenated_words = sol.findAllConcatenatedWordsInADict(words)
print("Concatenated Words:")
for word in concatenated_words:
print(word)import java.util.*;
class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEndOfWord = false;
}
public class Solution {
public void insert(TrieNode root, String word) {
TrieNode node = root;
for (char ch : word.toCharArray()) {
int index = ch - 'a';
if (node.children[index] == null) {
node.children[index] = new TrieNode();
}
node = node.children[index];
}
node.isEndOfWord = true;
}
public boolean dfs(TrieNode root, String word, int start, int count) {
if (start == word.length()) {
return count >= 2;
}
TrieNode node = root;
for (int i = start; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (node.children[index] == null) {
return false;
}
node = node.children[index];
if (node.isEndOfWord && dfs(root, word, i + 1, count + 1)) {
return true;
}
}
return false;
}
public List<String> findAllConcatenatedWordsInADict(String[] words) {
TrieNode root = new TrieNode();
for (String word : words) {
if (!word.isEmpty()) {
insert(root, word);
}
}
List<String> result = new ArrayList<>();
for (String word : words) {
if (dfs(root, word, 0, 0)) {
result.add(word);
}
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
String[] words = {"cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"};
List<String> concatenatedWords = sol.findAllConcatenatedWordsInADict(words);
System.out.println("Concatenated Words:");
concatenatedWords.forEach(System.out::println);
}
}#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
class TrieNode {
public:
TrieNode* children[26];
bool isEndOfWord;
TrieNode() {
for (int i = 0; i < 26; i++)
children[i] = nullptr;
isEndOfWord = false;
}
};
class Solution {
public:
void insert(TrieNode* root, const string& word) {
TrieNode* node = root;
for (char c : word) {
int index = c - 'a';
if (!node->children[index])
node->children[index] = new TrieNode();
node = node->children[index];
}
node->isEndOfWord = true;
}
bool dfs(TrieNode* root, const string& word, int start, int count) {
if (start == word.size())
return count >= 2;
TrieNode* node = root;
for (int i = start; i < word.size(); i++) {
int index = word[i] - 'a';
if (!node->children[index])
return false;
node = node->children[index];
if (node->isEndOfWord && dfs(root, word, i + 1, count + 1))
return true;
}
return false;
}
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
TrieNode* root = new TrieNode();
for (auto& word : words)
if (!word.empty())
insert(root, word);
vector<string> result;
for (auto& word : words)
if (dfs(root, word, 0, 0))
result.push_back(word);
return result;
}
};
// Usage example
int main() {
Solution sol;
vector<string> words = {"cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"};
vector<string> concatenatedWords = sol.findAllConcatenatedWordsInADict(words);
cout << "Concatenated Words:" << endl;
for (const string& word : concatenatedWords)
cout << word << endl;
return 0;
}class TrieNode {
constructor() {
this.children = {};
this.isEndOfWord = false;
}
}
class Solution {
insert(root, word) {
let node = root;
for (let char of word) {
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
}
node.isEndOfWord = true;
}
dfs(root, word, start, count) {
if (start === word.length) {
return count >= 2;
}
let node = root;
for (let i = start; i < word.length; i++) {
let char = word[i];
if (!node.children[char]) {
return false;
}
node = node.children[char];
if (node.isEndOfWord && this.dfs(root, word, i + 1, count + 1)) {
return true;
}
}
return false;
}
findAllConcatenatedWordsInADict(words) {
const root = new TrieNode();
for (let word of words) {
if (word.length > 0) {
this.insert(root, word);
}
}
const result = [];
for (let word of words) {
if (this.dfs(root, word, 0, 0)) {
result.push(word);
}
}
return result;
}
}
// Usage example
const solution = new Solution();
const words = ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"];
const concatenatedWords = solution.findAllConcatenatedWordsInADict(words);
console.log("Concatenated Words:");
concatenatedWords.forEach(word => console.log(word));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define ALPHABET_SIZE 26
// Trie Node structure
typedef struct TrieNode {
struct TrieNode* children[ALPHABET_SIZE];
bool isEndOfWord;
} TrieNode;
// Function to create a new Trie Node
TrieNode* createNode() {
TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
node->isEndOfWord = false;
for (int i = 0; i < ALPHABET_SIZE; i++)
node->children[i] = NULL;
return node;
}
// Function to insert a word into the Trie
void insert(TrieNode* root, const char* key) {
TrieNode* pCrawl = root;
while (*key) {
int index = *key - 'a';
if (!pCrawl->children[index])
pCrawl->children[index] = createNode();
pCrawl = pCrawl->children[index];
key++;
}
pCrawl->isEndOfWord = true;
}
// Helper function to determine if a word can be formed by other words
bool dfs(TrieNode* root, const char* word, int count) {
if (*word == '\0')
return count > 1;
TrieNode* pCrawl = root;
for (int i = 0; word[i]; i++) {
int index = word[i] - 'a';
if (pCrawl->children[index] == NULL)
return false;
pCrawl = pCrawl->children[index];
if (pCrawl->isEndOfWord) {
if (dfs(root, word + i + 1, count + 1))
return true;
}
}
return false;
}
// Function to find all concatenated words
char** findAllConcatenatedWords(char** words, int wordsSize, int* returnSize) {
TrieNode* root = createNode();
for (int i = 0; i < wordsSize; i++) {
if (strlen(words[i]) > 0)
insert(root, words[i]);
}
char** result = (char**)malloc(wordsSize * sizeof(char*));
*returnSize = 0;
for (int i = 0; i < wordsSize; i++) {
if (dfs(root, words[i], 0)) {
result[(*returnSize)++] = words[i];
}
}
return result;
}
// Usage example
int main() {
char* words[] = {"cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"};
int wordsSize = sizeof(words) / sizeof(words[0]);
int returnSize;
char** result = findAllConcatenatedWords(words, wordsSize, &returnSize);
printf("Concatenated Words: \n");
for (int i = 0; i < returnSize; i++) {
printf("%s\n", result[i]);
}
return 0;
}using System;
using System.Collections.Generic;
public class TrieNode {
public TrieNode[] Children = new TrieNode[26];
public bool IsEndOfWord;
}
public class Solution {
public void Insert(TrieNode root, string word) {
var node = root;
foreach (char c in word) {
int index = c - 'a';
if (node.Children[index] == null)
node.Children[index] = new TrieNode();
node = node.Children[index];
}
node.IsEndOfWord = true;
}
public bool Dfs(TrieNode root, string word, int start, int count) {
if (start == word.Length)
return count >= 2;
var node = root;
for (int i = start; i < word.Length; i++) {
int index = word[i] - 'a';
if (node.Children[index] == null)
return false;
node = node.Children[index];
if (node.IsEndOfWord && Dfs(root, word, i + 1, count + 1))
return true;
}
return false;
}
public List<string> FindAllConcatenatedWordsInADict(string[] words) {
TrieNode root = new TrieNode();
foreach (var word in words)
if (!string.IsNullOrEmpty(word))
Insert(root, word);
List<string> result = new List<string>();
foreach (var word in words)
if (Dfs(root, word, 0, 0))
result.Add(word);
return result;
}
public static void Main() {
Solution sol = new Solution();
string[] words = {"cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"};
List<string> concatenatedWords = sol.FindAllConcatenatedWordsInADict(words);
Console.WriteLine("Concatenated Words:");
foreach (var word in concatenatedWords)
Console.WriteLine(word);
}
}In this Python solution, a simple TrieNode class is defined to construct the Trie, and a solution class inserts each word into the Trie. Using depth-first search (DFS), it examines potential concatenations by checking if sub-words exist in the Trie.
Time Complexity: O(n * m^2), where n is the number of words and m is the average length of the words. The repeated DFS can lead to checking multiple permutations of concatenation.
Space Complexity: O(n * m) for the Trie, where n is the number of words and m is the average length.
Approach 2: Dynamic Programming
In this approach, dynamic programming (DP) is used to efficiently solve the problem of finding concatenated words. The idea is to treat each word as a state and store the results of subproblems to avoid repeated calculations. We iterate over each word and for each segment of the word, check if it can be split into valid sub-words based on previously computed results in the DP array.
This can be visualized as using a DP boolean array where each index represents if the word up to that index can be segmented into valid words in the list. This method is beneficial in reducing the number of redundant calculations.
def findAllConcatenatedWordsInADict(words):
word_set = set(words)
def is_concatenated(word):
if word in cache:
return cache[word]
n = len(word)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i):
if dp[j] and word[j:i] in word_set:
dp[i] = True
break
cache[word] = dp[n]
return dp[n]
result = []
cache = {}
for word in words:
word_set.remove(word)
if is_concatenated(word):
result.append(word)
word_set.add(word)
return result
# Usage example
if __name__ == "__main__":
words = ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"]
concatenated_words = findAllConcatenatedWordsInADict(words)
print("Concatenated Words:")
for word in concatenated_words:
print(word)import java.util.*;
public class Solution {
public List<String> findAllConcatenatedWordsInADict(String[] words) {
Set<String> dict = new HashSet<>(Arrays.asList(words));
List<String> result = new ArrayList<>();
for (String word : words) {
if (isConcatenatedWord(word, dict)) {
result.add(word);
}
}
return result;
}
private boolean isConcatenatedWord(String word, Set<String> dict) {
int n = word.length();
if (n == 0) return false;
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && dict.contains(word.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
public static void main(String[] args) {
Solution sol = new Solution();
String[] words = {"cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"};
List<String> concatenatedWords = sol.findAllConcatenatedWordsInADict(words);
System.out.println("Concatenated Words:");
concatenatedWords.forEach(System.out::println);
}
}#include <iostream>
#include <vector>
#include <unordered_set>
#include <string>
using namespace std;
bool isConcatenatedWord(const string& word, unordered_set<string>& dict) {
int n = word.size();
vector<bool> dp(n + 1, false);
dp[0] = true;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
if (dp[j] && dict.count(word.substr(j, i - j))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
unordered_set<string> dict(words.begin(), words.end());
vector<string> result;
for (const string& word : words) {
dict.erase(word);
if (isConcatenatedWord(word, dict)) {
result.push_back(word);
}
dict.insert(word);
}
return result;
}
// Usage example
int main() {
vector<string> words = {"cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"};
vector<string> concatenatedWords = findAllConcatenatedWordsInADict(words);
cout << "Concatenated Words:" << endl;
for (const string& word : concatenatedWords)
cout << word << endl;
return 0;
}function findAllConcatenatedWordsInADict(words) {
const wordSet = new Set(words);
function isConcatenated(word) {
const n = word.length;
const dp = Array(n + 1).fill(false);
dp[0] = true;
for (let i = 1; i <= n; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && wordSet.has(word.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
const result = [];
for (const word of words) {
wordSet.delete(word);
if (isConcatenated(word)) {
result.push(word);
}
wordSet.add(word);
}
return result;
}
// Usage example
const words = ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"];
const concatenatedWords = findAllConcatenatedWordsInADict(words);
console.log("Concatenated Words:");
concatenatedWords.forEach(word => console.log(word));#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
// Basic hashing function to create unique IDs for words
int hashCode(const char* key, int modulo) {
unsigned long hash = 5381;
int c;
while ((c = *key++))
hash = ((hash << 5) + hash) + c; // hash * 33 + c
return hash % modulo;
}
// Dynamic Word Dictionary using separate chaining for collision resolution
typedef struct Node {
char* key;
struct Node* next;
} Node;
void insertNode(Node** table, const char* key, int modulo) {
int hash = hashCode(key, modulo);
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->key = strdup(key);
newNode->next = table[hash];
table[hash] = newNode;
}
bool searchNode(Node** table, const char* key, int modulo) {
int hash = hashCode(key, modulo);
Node* node = table[hash];
while (node) {
if (strcmp(node->key, key) == 0)
return true;
node = node->next;
}
return false;
}
bool isConcatenatedWord(const char* word, Node** table, int modulo) {
int len = strlen(word);
if (len == 0) return false;
bool* dp = (bool*)calloc(len + 1, sizeof(bool));
dp[0] = true;
for (int i = 1; i <= len; i++) {
for (int j = 0; j < i; j++) {
if (dp[j]) {
char* subword = strndup(word + j, i - j);
if (searchNode(table, subword, modulo)) {
dp[i] = true;
free(subword);
break;
}
free(subword);
}
}
}
bool result = dp[len];
free(dp);
return result;
}
char** findAllConcatenatedWords(char** words, int wordsSize, int* returnSize) {
const int modulo = 10007;
Node** table = (Node**)calloc(modulo, sizeof(Node*));
for (int i = 0; i < wordsSize; i++) {
insertNode(table, words[i], modulo);
}
char** result = (char**)malloc(wordsSize * sizeof(char*));
*returnSize = 0;
for (int i = 0; i < wordsSize; i++) {
int len = strlen(words[i]);
// Temporarily remove the word from table for accurate concatenation check
insertNode(table, "", modulo); // dummy insert
if (isConcatenatedWord(words[i], table, modulo)) {
result[(*returnSize)++] = words[i];
}
insertNode(table, words[i], modulo); // Re-insert word
}
// Free the hash table
for (int i = 0; i < modulo; i++) {
Node* node = table[i];
while (node) {
Node* tmp = node;
node = node->next;
free(tmp->key);
free(tmp);
}
}
free(table);
return result;
}
// Usage example
int main() {
char* words[] = {"cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"};
int wordsSize = sizeof(words) / sizeof(words[0]);
int returnSize;
char** result = findAllConcatenatedWords(words, wordsSize, &returnSize);
printf("Concatenated Words: \n");
for (int i = 0; i < returnSize; i++) {
printf("%s\n", result[i]);
}
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public List<string> FindAllConcatenatedWordsInADict(string[] words) {
HashSet<string> dict = new HashSet<string>(words);
List<string> result = new List<string>();
foreach (var word in words) {
if (IsConcatenatedWord(word, dict)) {
result.Add(word);
}
}
return result;
}
private bool IsConcatenatedWord(string word, HashSet<string> dict) {
int n = word.Length;
if (n == 0) return false;
bool[] dp = new bool[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && dict.Contains(word.Substring(j, i - j))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
public static void Main(string[] args) {
Solution sol = new Solution();
string[] words = {"cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"};
List<string> concatenatedWords = sol.FindAllConcatenatedWordsInADict(words);
Console.WriteLine("Concatenated Words:");
foreach (var word in concatenatedWords)
Console.WriteLine(word);
}
}With the Python solution, a dynamic programming strategy marks possible word formations. Using a dictionary as a cache, it stores pre-computed results for efficiency when evaluating every word's ability to form concatenated forms by prefixes located in the set.
Time Complexity: O(n * m^2) because validating whether subsequences can form the input word requires traversal over segments.
Space Complexity: O(m) in memory used by the DP array to track the possible concatenation.
Approach 3: Default Approach
type Trie struct {
children [26]*Trie
isEnd bool
}
func newTrie() *Trie {
return &Trie{}
}
func (this *Trie) insert(word string) {
node := this
for _, c := range word {
c -= 'a'
if node.children[c] == nil {
node.children[c] = newTrie()
}
node = node.children[c]
}
node.isEnd = true
}
func findAllConcatenatedWordsInADict(words []string) (ans []string) {
sort.Slice(words, func(i, j int) bool { return len(words[i]) < len(words[j]) })
trie := newTrie()
var dfs func(string) bool
dfs = func(w string) bool {
if w == "" {
return true
}
node := trie
for i, c := range w {
c -= 'a'
if node.children[c] == nil {
return false
}
node = node.children[c]
if node.isEnd && dfs(w[i+1:]) {
return true
}
}
return false
}
for _, w := range words {
if dfs(w) {
ans = append(ans, w)
} else {
trie.insert(w)
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Trie and Depth-First Search (DFS) | Time Complexity: O(n * m^2), where n is the number of words and m is the average length of the words. The repeated DFS can lead to checking multiple permutations of concatenation. Space Complexity: O(n * m) for the Trie, where n is the number of words and m is the average length. |
| Dynamic Programming | Time Complexity: O(n * m^2) because validating whether subsequences can form the input word requires traversal over segments. Space Complexity: O(m) in memory used by the DP array to track the possible concatenation. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Trie + DFS | O(N * L^2) | O(N * L) | Large dictionaries with shared prefixes where trie prefix lookups reduce repeated substring checks |
| Dynamic Programming (Word Break style) | O(N * L^2) | O(L) | General interview solution; simpler implementation using hash set and prefix DP |
Frequently asked questions
Is Concatenated Words easy or hard?
Concatenated Words is classified as a hard problem because it combines multiple concepts: string segmentation, dynamic programming, recursion, and efficient dictionary lookups. Handling edge cases like preventing a word from using itself also increases implementation complexity.
Concatenated Words Python/Java solution
In Python or Java, the typical solution builds a set of words and applies dynamic programming to test each word. Alternatively, a trie combined with DFS checks prefixes and recursively validates the remaining substring. Both implementations achieve roughly O(N * L^2) complexity.
How to solve Concatenated Words in O(n)?
A strict O(n) solution is not typical because each word must evaluate multiple substring splits. The closest practical approach is O(N * L^2) using dynamic programming or trie-based DFS. Optimizations such as memoization and prefix pruning reduce redundant checks but do not eliminate the quadratic dependence on word length.
What is the best approach for Concatenated Words?
The most common solution uses dynamic programming similar to the Word Break problem. Words are processed from shortest to longest, and a DP array checks whether each prefix can be formed from existing dictionary entries. This approach runs in about O(N * L^2) time where N is the number of words and L is the maximum word length.
Is Concatenated Words asked at Google/Amazon/Meta?
Concatenated Words is considered a hard string and dynamic programming problem and appears in advanced interview rounds at companies like Google, Amazon, and Meta. It tests knowledge of word segmentation, trie structures, recursion, and optimization techniques.
What data structure is used in Concatenated Words?
Common data structures include a trie for fast prefix lookup and a hash set for constant-time dictionary membership checks. Dynamic programming arrays are used to track valid word break positions, while DFS recursion explores possible concatenation splits.
What is the time complexity of Concatenated Words?
Most optimal solutions run in O(N * L^2) time. Each word of length L is checked by evaluating multiple split points, and substring membership checks occur against a dictionary or trie. Space complexity ranges from O(L) for DP to O(N * L) when storing all words in a trie.