Word ladder

Hash Table String Breadth-First Search

44.9% acceptance

Jan 12, 2026

13432

1961

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that: Every adjacent pair of words differs by a single letter. Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList. sk == endWord Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn ladder_length(begin_word: String, end_word: String, word_list: Vec<String>) -> i32 {
    let end_idx = match word_list.iter().position(|w| w == &end_word) {
      Some(i) => i,
      None => return 0,
    };
    
    let n = word_list.len();
    let mut visited = vec![false; n];
    let mut curr = Vec::with_capacity(64);
    let mut next = Vec::with_capacity(64);
    
    let begin_bytes = begin_word.as_bytes();
    
    for i in 0..n {
      if Self::one_diff(begin_bytes, word_list[i].as_bytes()) {
        if i == end_idx {
          return 2;
        }
        visited[i] = true;
        curr.push(i);
      }
    }
    
    let mut level = 2;
    
    while !curr.is_empty() {
      level += 1;
      next.clear();
      
      for &idx in &curr {
        let bytes = word_list[idx].as_bytes();
        
        for i in 0..n {
          if visited[i] {
            continue;
          }
          
          if Self::one_diff(bytes, word_list[i].as_bytes()) {
            if i == end_idx {
              return level;
            }
            visited[i] = true;
            next.push(i);
          }
        }
      }
      
      std::mem::swap(&mut curr, &mut next);
    }
    
    0
  }
  
  #[inline]
  fn one_diff(a: &[u8], b: &[u8]) -> bool {
    let mut diffs = 0;
    for i in 0..a.len() {
      if a[i] != b[i] {
        diffs += 1;
        if diffs > 1 {
          return false;
        }
      }
    }
    diffs == 1
  }
}