Concatenated words

Array String Dynamic Programming Depth-First Search Trie Sorting

49.7% acceptance

Jan 13, 2026

4060

292

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::{HashSet, HashMap};

impl Solution {
  pub fn find_all_concatenated_words_in_a_dict(words: Vec<String>) -> Vec<String> {
    let word_set: HashSet<&str> = words.iter().map(|s| s.as_str()).collect();
    let mut result = Vec::new();
    
    for word in &words {
      let mut memo = HashMap::new();
      if Self::can_form(word, &word_set, 0, &mut memo) {
        result.push(word.clone());
      }
    }
    
    result
  }
  
  fn can_form(word: &str, word_set: &HashSet<&str>, start: usize, memo: &mut HashMap<usize, bool>) -> bool {
    if start == word.len() {
      return true;
    }
    
    if let Some(&cached) = memo.get(&start) {
      return cached;
    }
    
    let mut result = false;
    for end in (start + 1)..=word.len() {
      let sub = &word[start..end];
      // Skip if it's the whole word and we're at the start (need at least 2 parts)
      if sub == word {
        continue;
      }
      if word_set.contains(sub) && Self::can_form(word, word_set, end, memo) {
        result = true;
        break;
      }
    }
    
    memo.insert(start, result);
    result
  }
}