Longest word with all prefixes

Array String Depth-First Search Trie

72.1% acceptance

Mar 31, 2026

204

Given an array of strings words, find the longest string in words such that every prefix of it is also in words. For example, let words = ["a", "app", "ap"]. The string "app" has prefixes "ap" and "a", all of which are in words. Return the string described above. If there is more than one string with the same length, return the lexicographically smallest one, and if no string exists, return "".

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

use std::collections::HashSet;

impl Solution {
  pub fn longest_word(words: Vec<String>) -> String {
    let word_set: HashSet<&str> = words.iter().map(|s| s.as_str()).collect();
    let mut best = String::new();
    for word in &words {
      if (1..word.len()).all(|i| word_set.contains(&word[..i])) {
        if word.len() > best.len() || (word.len() == best.len() && *word < best) {
          best = word.clone();
        }
      }
    }
    best
  }
}