Problem

Given an array of words, find the longest word that can be constructed by concatenating other words from the same array (each word can be used multiple times, but not itself as a whole). If there are multiple answers, return any one of them.

Examples

Example 1

1
2
3

Input: ["test", "tester", "testertest", "testing", "testingtester"]
Output: "testingtester"
Explanation: "testingtester" = "testing" + "tester".

Example 2

1
2
3

Input: ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"]
Output: "ratcatdogcat"
Explanation: "ratcatdogcat" = "rat" + "cat" + "dog" + "cat".

Solution

Method 1 – Sort and Greedy Check

Intuition

By sorting the words by length (longest first), we can check each word to see if it can be formed by concatenating other words in the array. The first such word found will be the longest.

Approach

  1. Sort the array of words in descending order by length.
  2. For each word in the sorted list:
    • Check if it can be formed by concatenating other words from the array (excluding itself as a whole).
    • If yes, return this word as the answer.
  3. If no such word exists, return an empty string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    string longestCompoundWord(vector<string>& words) {
        sort(words.begin(), words.end(), [](const string& a, const string& b) {
            return a.size() > b.size();
        });
        unordered_set<string> wordSet(words.begin(), words.end());
        for (const string& word : words) {
            wordSet.erase(word);
            if (canForm(word, wordSet)) return word;
            wordSet.insert(word);
        }
        return "";
    }
    bool canForm(const string& word, unordered_set<string>& wordSet) {
        if (wordSet.empty()) return false;
        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] && wordSet.count(word.substr(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func LongestCompoundWord(words []string) string {
    sort.Slice(words, func(i, j int) bool { return len(words[i]) > len(words[j]) })
    wordSet := make(map[string]struct{})
    for _, w := range words { wordSet[w] = struct{}{} }
    for _, word := range words {
        delete(wordSet, word)
        if canForm(word, wordSet) { return word }
        wordSet[word] = struct{}{}
    }
    return ""
}
func canForm(word string, wordSet map[string]struct{}) bool {
    if len(wordSet) == 0 { return false }
    n := len(word)
    dp := make([]bool, n+1)
    dp[0] = true
    for i := 1; i <= n; i++ {
        for j := 0; j < i; j++ {
            if dp[j] {
                if _, ok := wordSet[word[j:i]]; ok {
                    dp[i] = true
                    break
                }
            }
        }
    }
    return dp[n]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    public String longestCompoundWord(String[] words) {
        Arrays.sort(words, (a, b) -> b.length() - a.length());
        Set<String> wordSet = new HashSet<>(Arrays.asList(words));
        for (String word : words) {
            wordSet.remove(word);
            if (canForm(word, wordSet)) return word;
            wordSet.add(word);
        }
        return "";
    }
    private boolean canForm(String word, Set<String> wordSet) {
        if (wordSet.isEmpty()) return false;
        int n = word.length();
        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] && wordSet.contains(word.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def longest_compound_word(self, words: list[str]) -> str:
        words.sort(key=len, reverse=True)
        word_set = set(words)
        for word in words:
            word_set.remove(word)
            if self.can_form(word, word_set):
                return word
            word_set.add(word)
        return ""
    def can_form(self, word: str, word_set: set[str]) -> bool:
        if not word_set:
            return False
        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
        return dp[n]

Complexity

  • ⏰ Time complexity: O(n * L^2), where n is the number of words and L is the maximum word length (for each word, we check all possible splits).
  • 🧺 Space complexity: O(n * L), for the set and DP array.

Method 2 – Trie-Based Recursive Search

Intuition

A Trie can efficiently store all words and allow recursive search to check if a word can be formed by concatenating other words.

Approach

  1. Build a Trie from all words in the array.
  2. Sort the words by length (longest first).
  3. For each word, recursively check if it can be formed by concatenating other words using the Trie.
  4. Return the first such word found.

(Code omitted for brevity; see references for details.)

Complexity

  • ⏰ Time complexity: O(n * L^2), similar to the DP approach, but with better constant factors for prefix checks.
  • 🧺 Space complexity: O(n * L), for the Trie.