Shortest word distance ii

Array Hash Table Two Pointers String Design

62.8% acceptance

Mar 31, 2026

1086

403

Design a data structure that will be initialized with a string array, and then it should answer queries of the shortest distance between two different strings from the array. Implement the WordDistance class: WordDistance(String[] wordsDict) initializes the object with the strings array wordsDict. int shortest(String word1, String word2) returns the shortest distance between word1 and word2 in the array wordsDict.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

struct WordDistance {
  map: HashMap<String, Vec<i32>>,
}

impl WordDistance {
  fn new(words_dict: Vec<String>) -> Self {
    let mut map: HashMap<String, Vec<i32>> = HashMap::new();
    for (i, w) in words_dict.into_iter().enumerate() {
      map.entry(w).or_default().push(i as i32);
    }
    WordDistance { map }
  }
  
  fn shortest(&self, word1: String, word2: String) -> i32 {
    let l1 = &self.map[&word1];
    let l2 = &self.map[&word2];
    let (mut i, mut j) = (0, 0);
    let mut min_dist = i32::MAX;
    while i < l1.len() && j < l2.len() {
      min_dist = min_dist.min((l1[i] - l2[j]).abs());
      if l1[i] < l2[j] {
        i += 1;
      } else {
        j += 1;
      }
    }
    min_dist
  }
}

/*
 * Your WordDistance object will be instantiated and called as such:
 * let obj = WordDistance::new(wordsDict);
 * let ret_1: i32 = obj.shortest(word1, word2);
 */