472. Concatenated Words LeetCode Solution

In this guide, you will get 472. Concatenated Words LeetCode Solution with the best time and space complexity. The solution to Concatenated Words problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Concatenated Words solution in C++
Concatenated Words solution in Java
Concatenated Words solution in Python
Additional Resources

472. Concatenated Words LeetCode Solution image

Problem Statement of Concatenated Words

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 <= 104
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) <= 105

Complexity Analysis

Time Complexity: O(n\ell^3), where n = |\texttt{words}| and \ell = \max(|\texttt{words[i]}|)
Space Complexity: O(n\ell)

472. Concatenated Words LeetCode Solution in C++

class Solution {
 public:
  vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
    vector<string> ans;
    unordered_set<string> wordSet{words.begin(), words.end()};
    unordered_map<string, bool> mem;

    for (const string& word : words)
      if (isConcat(word, wordSet, mem))
        ans.push_back(word);

    return ans;
  }

 private:
  bool isConcat(const string& s, const unordered_set<string>& wordSet,
                unordered_map<string, bool>& mem) {
    if (const auto it = mem.find(s); it != mem.cend())
      return it->second;

    for (int i = 1; i < s.length(); ++i) {
      const string prefix = s.substr(0, i);
      const string suffix = s.substr(i);
      if (wordSet.contains(prefix) &&
          (wordSet.contains(suffix) || isConcat(suffix, wordSet, mem)))
        return mem[s] = true;
    }

    return mem[s] = false;
  }
};
/* code provided by PROGIEZ */

472. Concatenated Words LeetCode Solution in Java

class Solution {
  public List<String> findAllConcatenatedWordsInADict(String[] words) {
    List<String> ans = new ArrayList<>();
    Set<String> wordSet = new HashSet<>(Arrays.asList(words));
    Map<String, Boolean> mem = new HashMap<>();

    for (final String word : words)
      if (wordBreak(word, wordSet, mem))
        ans.add(word);

    return ans;
  }

  private boolean wordBreak(final String word, Set<String> wordSet, Map<String, Boolean> mem) {
    if (mem.containsKey(word))
      return mem.get(word);

    for (int i = 1; i < word.length(); ++i) {
      final String prefix = word.substring(0, i);
      final String suffix = word.substring(i);
      if (wordSet.contains(prefix) &&
          (wordSet.contains(suffix) || wordBreak(suffix, wordSet, mem))) {
        mem.put(word, true);
        return true;
      }
    }

    mem.put(word, false);
    return false;
  }
}
// code provided by PROGIEZ

472. Concatenated Words LeetCode Solution in Python

class Solution:
  def findAllConcatenatedWordsInADict(self, words: list[str]) -> list[str]:
    wordSet = set(words)

    @functools.lru_cache(None)
    def isConcat(word: str) -> bool:
      for i in range(1, len(word)):
        prefix = word[:i]
        suffix = word[i:]
        if prefix in wordSet and (suffix in wordSet or isConcat(suffix)):
          return True

      return False

    return [word for word in words if isConcat(word)]
 # code by PROGIEZ