Welcome to Subscribe On Youtube

472. Concatenated Words

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.

 

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

Solutions

• Java
• C++
• Python
• Go

• class Trie {
      Trie[] children = new Trie[26];
      boolean isEnd;
  
      void insert(String w) {
          Trie node = this;
          for (char c : w.toCharArray()) {
              c -= 'a';
              if (node.children[c] == null) {
                  node.children[c] = new Trie();
              }
              node = node.children[c];
          }
          node.isEnd = true;
      }
  }
  
  class Solution {
      private Trie trie = new Trie();
  
      public List<String> findAllConcatenatedWordsInADict(String[] words) {
          Arrays.sort(words, (a, b) -> a.length() - b.length());
          List<String> ans = new ArrayList<>();
          for (String w : words) {
              if (dfs(w)) {
                  ans.add(w);
              } else {
                  trie.insert(w);
              }
          }
          return ans;
      }
  
      private boolean dfs(String w) {
          if ("".equals(w)) {
              return true;
          }
          Trie node = trie;
          for (int i = 0; i < w.length(); ++i) {
              int idx = w.charAt(i) - 'a';
              if (node.children[idx] == null) {
                  return false;
              }
              node = node.children[idx];
              if (node.isEnd && dfs(w.substring(i + 1))) {
                  return true;
              }
          }
          return false;
      }
  }
  

• class Trie {
  public:
      vector<Trie*> children;
      bool isEnd;
      Trie()
          : children(26)
          , isEnd(false) {}
  
      void insert(string w) {
          Trie* node = this;
          for (char c : w) {
              c -= 'a';
              if (!node->children[c]) node->children[c] = new Trie();
              node = node->children[c];
          }
          node->isEnd = true;
      }
  };
  
  class Solution {
  public:
      Trie* trie = new Trie();
  
      vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
          sort(words.begin(), words.end(), [&](const string& a, const string& b) {
              return a.size() < b.size();
          });
          vector<string> ans;
          for (auto& w : words) {
              if (dfs(w))
                  ans.push_back(w);
              else
                  trie->insert(w);
          }
          return ans;
      }
  
      bool dfs(string w) {
          if (w == "") return true;
          Trie* node = trie;
          for (int i = 0; i < w.size(); ++i) {
              int idx = w[i] - 'a';
              if (!node->children[idx]) return false;
              node = node->children[idx];
              if (node->isEnd && dfs(w.substr(i + 1))) return true;
          }
          return false;
      }
  };
  

• class Trie:
      def __init__(self):
          self.children = [None] * 26
          self.is_end = False
  
      def insert(self, w):
          node = self
          for c in w:
              idx = ord(c) - ord('a')
              if node.children[idx] is None:
                  node.children[idx] = Trie()
              node = node.children[idx]
          node.is_end = True
  
  
  class Solution:
      def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
          def dfs(w):
              if not w:
                  return True
              node = trie
              for i, c in enumerate(w):
                  idx = ord(c) - ord('a')
                  if node.children[idx] is None:
                      return False
                  node = node.children[idx]
                  if node.is_end and dfs(w[i + 1 :]):
                      return True
              return False
  
          trie = Trie()
          ans = []
          words.sort(key=lambda x: len(x))
          for w in words:
              if dfs(w):
                  ans.append(w)
              else:
                  trie.insert(w)
          return ans
  
  

• type Trie struct {
  	children [26]*Trie
  	isEnd    bool
  }
  
  func newTrie() *Trie {
  	return &Trie{}
  }
  func (this *Trie) insert(word string) {
  	node := this
  	for _, c := range word {
  		c -= 'a'
  		if node.children[c] == nil {
  			node.children[c] = newTrie()
  		}
  		node = node.children[c]
  	}
  	node.isEnd = true
  }
  
  func findAllConcatenatedWordsInADict(words []string) (ans []string) {
  	sort.Slice(words, func(i, j int) bool { return len(words[i]) < len(words[j]) })
  	trie := newTrie()
  	var dfs func(string) bool
  	dfs = func(w string) bool {
  		if w == "" {
  			return true
  		}
  		node := trie
  		for i, c := range w {
  			c -= 'a'
  			if node.children[c] == nil {
  				return false
  			}
  			node = node.children[c]
  			if node.isEnd && dfs(w[i+1:]) {
  				return true
  			}
  		}
  		return false
  	}
  	for _, w := range words {
  		if dfs(w) {
  			ans = append(ans, w)
  		} else {
  			trie.insert(w)
  		}
  	}
  	return
  }
  

All Problems

All Solutions