Before and after puzzle

Array Hash Table String Sorting

51.8% acceptance

Mar 31, 2026

158

Given a list of phrases, generate a list of Before and After puzzles. A phrase is a string that consists of lowercase English letters and spaces only. No space appears in the start or the end of a phrase. There are no consecutive spaces in a phrase. Before and After puzzles are phrases that are formed by merging two phrases where the last word of the first phrase is the same as the first word of the second phrase. Note that only the last word of the first phrase and the first word of the second phrase are merged in this process. Return the Before and After puzzles that can be formed by every two phrases phrases[i] and phrases[j] where i != j. Note that the order of matching two phrases matters, we want to consider both orders. You should return a list of distinct strings sorted lexicographically, after removing all duplicate phrases in the generated Before and After puzzles.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn before_and_after_puzzles(phrases: Vec<String>) -> Vec<String> {
    use std::collections::BTreeSet;
    let n = phrases.len();
    let first_words: Vec<&str> = phrases.iter().map(|p| p.split(' ').next().unwrap()).collect();
    let last_words: Vec<&str> = phrases.iter().map(|p| p.rsplit(' ').next().unwrap()).collect();
    let mut result = BTreeSet::new();
    for i in 0..n {
      for j in 0..n {
        if i != j && last_words[i] == first_words[j] {
          // Merge: phrases[i] + rest of phrases[j] (skip first word)
          let rest = &phrases[j][first_words[j].len()..];
          let merged = format!("{}{}", phrases[i], rest);
          result.insert(merged);
        }
      }
    }
    result.into_iter().collect()
  }
}