Concatenated Words

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 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 <= 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

Try this Problem on your own or check similar problems:

Word Break II

Solution:

Java
JavaScript
Python
C++

class Solution {
    class Trie {
      public class TrieNode{
        TrieNode[] children;
        boolean isWord = false;
        public TrieNode(){
          children = new TrieNode[26];
        }
      }

      TrieNode root;
      public Trie() {
        root = new TrieNode();
      }

      public void insert(String word) {
        TrieNode iter = root;
        for(int i = 0; i < word.length(); ++i){
          char letter = word.charAt(i);
          if(iter.children[letter - 'a'] == null){
            iter.children[letter - 'a'] = new TrieNode();
          }
          iter = iter.children[letter - 'a'];
        }
        iter.isWord = true;
      }

      private boolean isConcatenated(String word, TrieNode iter, int index, int numberOfWords){
          if(index == word.length()) return numberOfWords > 1;

          for(int i = index; i < word.length(); ++i){
              char c = word.charAt(i);
              if(iter.children[c - 'a'] == null) return false;

              iter = iter.children[c - 'a'];
              if(iter.isWord && isConcatenated(word, root, i + 1, numberOfWords + 1)){
                  return true;
              }
          }

          return false;
      }
    }



    public List<String> findAllConcatenatedWordsInADict(String[] words) {
      Trie trie = new Trie();
      List<String> result = new ArrayList<>();

      for(String word: words){
          trie.insert(word);
      }

      for(String word: words){
          if(trie.isConcatenated(word, trie.root, 0, 0)) result.add(word);
      }

      return result;
    }
}

/**
 * @param {string[]} words
 * @return {string[]}
 */
var findAllConcatenatedWordsInADict = function (words) {
  const trie = new Trie();
  const result = [];

  for (const word of words) {
    trie.insert(word);
  }

  for (const word of words) {
    if (trie.isConcatenated(word, trie.root, 0, 0)) result.push(word);
  }

  return result;
};

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let iter = this.root;
    for (let i = 0; i < word.length; i++) {
      const letter = word.charAt(i);
      if (iter.children[letter.charCodeAt(0) - 97] == null) {
        iter.children[letter.charCodeAt(0) - 97] = new TrieNode();
      }
      iter = iter.children[letter.charCodeAt(0) - 97];
    }
    iter.isWord = true;
  }

  isConcatenated(word, iter, index, numberOfWords) {
    if (index === word.length) return numberOfWords > 1;

    for (let i = index; i < word.length; i++) {
      const c = word.charAt(i);
      if (iter.children[c.charCodeAt(0) - 97] == null) return false;

      iter = iter.children[c.charCodeAt(0) - 97];
      if (
        iter.isWord &&
        this.isConcatenated(word, this.root, i + 1, numberOfWords + 1)
      ) {
        return true;
      }
    }

    return false;
  }
}

class TrieNode {
  constructor() {
    this.children = Array(26).fill(null);
    this.isWord = false;
    this.word = "";
  }
}

class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
      trie = Trie()
      result = []

      for word in words:
        trie.insert(word)

      for word in words:
        if trie.isConcatenated(word, trie.root, 0, 0):
          result.append(word)

      return result

class Trie:
  class TrieNode:
    def __init__(self):
      self.children = [None] * 26
      self.isWord = False

  def __init__(self):
    self.root = self.TrieNode()

  def insert(self, word):
    iter = self.root
    for i in range(len(word)):
      letter = word[i]
      if iter.children[ord(letter) - ord('a')] is None:
        iter.children[ord(letter) - ord('a')] = self.TrieNode()
      iter = iter.children[ord(letter) - ord('a')]
    iter.isWord = True

  def isConcatenated(self, word, iter, index, numberOfWords):
    if index == len(word):
      return numberOfWords > 1

    for i in range(index, len(word)):
      c = word[i]
      if iter.children[ord(c) - ord('a')] is None:
        return False

      iter = iter.children[ord(c) - ord('a')]
      if iter.isWord and self.isConcatenated(word, self.root, i + 1, numberOfWords + 1):
        return True

    return False

class Trie {
private:
  class TrieNode {
  public:
    TrieNode* children[26];
    bool isWord;

    TrieNode() {
      for (int i = 0; i < 26; i++) {
        children[i] = nullptr;
      }
      isWord = false;
    }
  };

public:
  TrieNode* root;
  Trie() {
    root = new TrieNode();
  }

  void insert(string word) {
    TrieNode* iter = root;
    for (char letter : word) {
      if (iter->children[letter - 'a'] == nullptr) {
        iter->children[letter - 'a'] = new TrieNode();
      }
      iter = iter->children[letter - 'a'];
    }
    iter->isWord = true;
  }

  bool isConcatenated(string word, TrieNode* iter, int index, int numberOfWords) {
    if (index == word.length()) {
      return numberOfWords > 1;
    }

    for (int i = index; i < word.length(); i++) {
      char c = word[i];
      if (iter->children[c - 'a'] == nullptr) {
        return false;
      }

      iter = iter->children[c - 'a'];
      if (iter->isWord && isConcatenated(word, root, i + 1, numberOfWords + 1)) {
        return true;
      }
    }

    return false;
  }
};

class Solution {
public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
      Trie trie;
      vector<string> result;

      for (string word : words) {
        trie.insert(word);
      }

      for (string word : words) {
        if (trie.isConcatenated(word, trie.root, 0, 0)) {
          result.push_back(word);
        }
      }

      return result;
    }
};

Time/Space Complexity:

Time Complexity: O(nk*n)
Space Complexity: O(nk)

Explanation:

We use the same Trie approach we have already used in Implement Trie (Prefix Tree) and Longest Word in Dictionary. It takes n * k time to build and traverse the trie where n is the number of words while k is the average or maximum length of given words so the time complexity is O(nk), we have the same for space complexity since the number of nodes will be equal to sum of all word lengths (we can take average or maximum length word to define upper boundary). For the time complexity we also we have the multiplier n since we perform traversal n times (we traverse for every word) and in the worst-case scenario we would be visiting all nodes in the trie for each traversal. The bulk of the algorithm is isConcatenated search where try to break the current word in other words in the trie while counting the total number of words we used numberOfWords.

Example 1:​

Example 2:​

Constraints:​

Solution:​

Time/Space Complexity:​