Skip to main content

Concatenated Words

Problem Descriptionā€‹

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.

Examplesā€‹

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 <= 10^4
  • 1 <= words[i].length <= 30
  • words[i] consists of only lowercase English letters.
  • All the strings of words are unique.
  • 1 <= sum(words[i].length) <= 10^5

Solution for Concatenated Wordsā€‹

Intuitionā€‹

  • The main intuition behind this solution is to use dynamic programming to check if a word can be split into smaller words that are all present in the dictionary. By recursively checking each substring and memoizing the results, we can efficiently determine if a word is a concatenated word.

Approachā€‹

  • Dictionary Setup: Store all words from the input words vector into a set mp for quick lookup. This set will help in O(1) average time complexity for checking if a substring is a valid word.

Recursive Function (solve):ā€‹

  • Parameters: The function solve takes the word (op), the current index (idx), the count of words found so far (cnt), and a memoization vector (memo).
  • Base Case: If idx reaches the end of the word (op.size()), it checks if the count of words (cnt) is at least 2. This ensures that the word is formed by concatenating at least two smaller words.
  • Memoization Check: If the result for the current index is already computed (memo[idx] != -1), return the stored result to avoid redundant calculations.
  • Substring Generation: Iterate from the current index to the end of the word, generating substrings (temp). For each substring, check if it exists in the set mp.
  • Recursive Check: If a valid substring is found, recursively call solve on the remaining part of the word (i + 1). If this recursive call returns true, store the result in memo[idx] and return true.

Main Function (findAllConcatenatedWordsInADict):ā€‹

  • Initialization: Initialize an empty vector ans to store the result and populate the set mp with all words from the input.

  • Processing Each Word: For each word in the input:

  • Initialize a memoization vector memo with -1 indicating that no computations have been done for those indices.

  • Call the solve function starting from index 0 and count 0.

  • If solve returns true, add the word to the result vector ans.

  • Return Result: After processing all words, return the result vector ans containing all concatenated words.

Implementationā€‹

Live Editor
function Solution() {
const findAllConcatenatedWordsInADict = (words) => {
    const st = new Set(words);

    const solve = (op, idx, cnt, memo) => {
        if (idx === op.length) {
            return cnt >= 2;
        }

        if (memo[idx] !== -1) {
            return memo[idx] === 1;
        }

        let temp = "";
        for (let i = idx; i < op.length; i++) {
            temp += op[i];
            if (st.has(temp)) {
                if (solve(op, i + 1, cnt + 1, memo)) {
                    memo[idx] = 1;
                    return true;
                }
            }
        }
        memo[idx] = 0;
        return false;
    };

    const ans = [];
    for (const word of words) {
        const memo = new Array(word.length).fill(-1);
        if (solve(word, 0, 0, memo)) {
            ans.push(word);
        }
    }
    return ans;
};

const input = ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"];
const output = findAllConcatenatedWordsInADict(input);
  return (
    <div>
      <p>
        <b>Input: </b>{JSON.stringify(input)}
      </p>
      <p>
        <b>Output:</b> {output.toString()}
      </p>
    </div>
  );
}
Result
Loading...

Code in Different Languagesā€‹

Written by @hiteshgahanolia
const findAllConcatenatedWordsInADict = (words) => {
const st = new Set(words);

const solve = (op, idx, cnt, memo) => {
if (idx === op.length) {
return cnt >= 2;
}

if (memo[idx] !== -1) {
return memo[idx] === 1;
}

let temp = "";
for (let i = idx; i < op.length; i++) {
temp += op[i];
if (st.has(temp)) {
if (solve(op, i + 1, cnt + 1, memo)) {
memo[idx] = 1;
return true;
}
}
}
memo[idx] = 0;
return false;
};

const ans = [];
for (const word of words) {
const memo = new Array(word.length).fill(-1);
if (solve(word, 0, 0, memo)) {
ans.push(word);
}
}
return ans;
};

Complexity Analysisā€‹

Time Complexity:ā€‹
Initialization:ā€‹
  • Inserting all words into the set st takes O(Nā‹…L)O(Nā‹…L) time, where N is the number of words and L is the average length of the words. This is because each word of length L takes O(L)O(L) time to insert into the set.
Main Loop:ā€‹
  • For each word, we call the solve function which performs a recursive check. There are N words, and for each word of length L, the solve function is called.
Recursive Function (solve):ā€‹
  • In the worst case, the solve function examines each possible substring of the word. This can involve (L2)(L^2) substrings in the worst case (considering all possible start and end points of substrings).For each substring, we check if it exists in the set st, which takes O(1)O(1) time on average.
  • The memoization array ensures that each index is only computed once, so each index computation takes O(L)O(L) time.
Space Complexity:ā€‹
Set (st):ā€‹
  • Storing all words in the set takes O(Nā‹…L)O(Nā‹…L) space.
Memoization Array:ā€‹
  • For each word of length L, the memoization array takes O(L)O(L) space.In the worst case, all N words are of length L, so the total space required for memoization is O(Nā‹…L)O(Nā‹…L).
Recursive Call Stack:ā€‹
  • The depth of the recursion is at most L (the length of the longest word), so the space used by the call stack is O(L)O(L).
Combining these:ā€‹
  • The total space complexity is O(Nā‹…L)O(Nā‹…L) due to the set and memoization array.

Referencesā€‹