Concatenated Words - Practice Coding Problems

Concatenated Words - Problem

Array String Dynamic Programming Depth-First Search Trie Sorting Hard

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.

Input & Output

Example 1 — Multiple Concatenated Words

$ Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]

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

💡 Note: "catsdogcats" = "cats" + "dog" + "cats", "dogcatsdog" = "dog" + "cats" + "dog", "ratcatdogcat" = "rat" + "cat" + "dog" + "cat"

Example 2 — No Concatenated Words

$ Input: words = ["cat","dog","bird"]

› Output: []

💡 Note: None of the words can be formed by concatenating other words in the array

Example 3 — Self-Concatenation

$ Input: words = ["a","aa","aaa"]

› Output: ["aa","aaa"]

💡 Note: "aa" = "a" + "a", "aaa" = "a" + "aa" or "aa" + "a"

Constraints

1 ≤ words.length ≤ 10⁴
1 ≤ words[i].length ≤ 30
words[i] consists of only lowercase English letters
All the strings of words are unique

Visualization

Tap to expand

Understanding the Visualization

Input

Array of unique words to analyze

Process

Check each word to see if it can be split into existing words

Output

Return all words that are concatenations of at least 2 others

Key Takeaway

🎯 Key Insight: Sort by length and use DP to check if each word can be built from previously processed shorter words

Asked in

a Amazon 35 G Google 28 M Microsoft 22 f Facebook 18

The key insight is to recognize this as a word break problem where we need to check if each word can be decomposed into at least 2 other words. The best approach uses dynamic programming with sorting or Trie with DFS. Time: O(n × m³), Space: O(n + m).

Common Approaches

Approach	Time	Space	Notes
✓ Memoization (Top-Down DP)	O(n × m³)	O(n + m)	Use recursion with memoization to avoid redundant calculations
Optimized with Trie + DFS	O(n × m²)	O(n × m)	Use Trie data structure with DFS for efficient word composition checking
Dynamic Programming (Bottom-Up)	O(n × m³)	O(n + m)	Use 1D DP array to build up solutions for each word iteratively
Brute Force with Recursion	O(2ⁿ)	O(n + m)	For each word, try all possible splits and recursively check if parts exist

Memoization (Top-Down DP) — Algorithm Steps

Create a memoization cache for processed words
For each word, use recursive function with memo
Cache results to avoid recomputing same subproblems
Return all words that can be formed from at least 2 other words

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_WORDS 1000
#define MAX_LEN 1000
#define MEMO_SIZE 10000

char words[MAX_WORDS][MAX_LEN];
int wordCount = 0;
char memoKeys[MEMO_SIZE][MAX_LEN];
bool memoVals[MEMO_SIZE];
int memoCount = 0;

bool wordExists(const char* word) {
    for (int i = 0; i < wordCount; i++) {
        if (strcmp(words[i], word) == 0) {
            return true;
        }
    }
    return false;
}

bool getMemo(const char* key) {
    for (int i = 0; i < memoCount; i++) {
        if (strcmp(memoKeys[i], key) == 0) {
            return memoVals[i];
        }
    }
    return false;
}

void setMemo(const char* key, bool val) {
    strcpy(memoKeys[memoCount], key);
    memoVals[memoCount] = val;
    memoCount++;
}

bool hasMemo(const char* key) {
    for (int i = 0; i < memoCount; i++) {
        if (strcmp(memoKeys[i], key) == 0) {
            return true;
        }
    }
    return false;
}

bool canForm(const char* word, int count) {
    char key[MAX_LEN + 10];
    sprintf(key, "%s|%d", word, count);
    
    if (hasMemo(key)) {
        return getMemo(key);
    }
    
    if (count > 0 && wordExists(word)) {
        setMemo(key, true);
        return true;
    }
    
    int len = strlen(word);
    for (int i = 1; i < len; i++) {
        char prefix[MAX_LEN], suffix[MAX_LEN];
        strncpy(prefix, word, i);
        prefix[i] = '\0';
        strcpy(suffix, word + i);
        
        if (wordExists(prefix) && canForm(suffix, count + 1)) {
            setMemo(key, true);
            return true;
        }
    }
    
    setMemo(key, false);
    return false;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple JSON parsing for array of strings
    char* token = strtok(line, "[]\",");
    while (token != NULL) {
        if (strlen(token) > 0 && strcmp(token, " ") != 0 && strcmp(token, "\n") != 0) {
            strcpy(words[wordCount++], token);
        }
        token = strtok(NULL, "[]\",");
    }
    
    printf("[");
    bool first = true;
    for (int i = 0; i < wordCount; i++) {
        if (canForm(words[i], 0)) {
            if (!first) printf(",");
            printf("\"%s\"", words[i]);
            first = false;
        }
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m³)

For each of n words, we check all m² possible splits, each taking O(m) time

✓ Linear Growth

Space Complexity

O(n + m)

Memoization cache stores results for processed words, recursion depth up to m

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~35 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen