Word abbreviation

Array String Greedy Trie Sorting

62.7% acceptance

Mar 31, 2026

405

300

Given an array of distinct strings words, return the minimal possible abbreviations for every word. The following are the rules for a string abbreviation: The initial abbreviation for each word is: the first character, then the number of characters in between, followed by the last character. If more than one word shares the same abbreviation, then perform the following operation: Increase the prefix (characters in the first part) of each of their abbreviations by 1. For example, say you start with the words ["abcdef","abndef"] both initially abbreviated as "a4f". Then, a sequence of operations would be ["a4f","a4f"] -> ["ab3f","ab3f"] -> ["abc2f","abn2f"]. This operation is repeated until every abbreviation is unique. At the end, if an abbreviation did not make a word shorter, then keep it as the original word.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn words_abbreviation(words: Vec<String>) -> Vec<String> {
    use std::collections::HashMap;
    let n = words.len();
    let mut prefix = vec![1usize; n];
    let mut result: Vec<String> = words.iter().enumerate().map(|(i, w)| Self::abbrev(w, prefix[i])).collect();
    
    loop {
      let mut changed = false;
      let mut groups: HashMap<String, Vec<usize>> = HashMap::new();
      for i in 0..n {
        groups.entry(result[i].clone()).or_default().push(i);
      }
      for (_abbr, indices) in &groups {
        if indices.len() > 1 {
          changed = true;
          for &i in indices {
            prefix[i] += 1;
            result[i] = Self::abbrev(&words[i], prefix[i]);
            if result[i].len() >= words[i].len() {
              result[i] = words[i].clone();
            }
          }
        }
      }
      if !changed { break; }
    }
    result
  }
  
  fn abbrev(word: &str, prefix_len: usize) -> String {
    let n = word.len();
    if prefix_len + 2 >= n {
      return word.to_string();
    }
    format!("{}{}{}", &word[..prefix_len], n - prefix_len - 1, &word[n-1..n])
  }
}