Word ladder ii

Hash Table String Backtracking Breadth-First Search

27.5% acceptance

Jan 12, 2026

6533

834

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 all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s1, s2, ..., sk].

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_ladders(begin_word: String, end_word: String, word_list: Vec<String>) -> Vec<Vec<String>> {
    use std::collections::{HashMap, VecDeque};
    
    let mut words = word_list;
    let end_idx = match words.iter().position(|w| w == &end_word) {
      Some(i) => i,
      None => return vec![],
    };
    
    let begin_idx = match words.iter().position(|w| w == &begin_word) {
      Some(i) => i,
      None => {
        words.push(begin_word.clone());
        words.len() - 1
      }
    };
    
    let word_len = words[0].len();
    let n = words.len();
    
    // Build pattern map
    let mut pattern_map: HashMap<[u8; 6], Vec<u16>> = HashMap::with_capacity(n * word_len);
    
    for (idx, word) in words.iter().enumerate() {
      let bytes = word.as_bytes();
      for i in 0..word_len {
        let mut pattern = [0u8; 6];
        unsafe {
          std::ptr::copy_nonoverlapping(bytes.as_ptr(), pattern.as_mut_ptr(), i);
          *pattern.get_unchecked_mut(i) = b'*';
          std::ptr::copy_nonoverlapping(bytes.as_ptr().add(i+1), pattern.as_mut_ptr().add(i+1), word_len-i-1);
        }
        pattern_map.entry(pattern).or_insert_with(Vec::new).push(idx as u16);
      }
    }
    
    // BFS
    let mut queue = VecDeque::with_capacity(n);
    queue.push_back(begin_idx as u16);
    
    let mut dist = vec![u16::MAX; n];
    unsafe { *dist.get_unchecked_mut(begin_idx) = 0; }
    
    let mut parents: Vec<Vec<u16>> = vec![Vec::new(); n];
    
    while let Some(word_idx) = queue.pop_front() {
      let wi = word_idx as usize;
      let curr_dist = unsafe { *dist.get_unchecked(wi) };
      
      if wi == end_idx {
        break;
      }
      
      let bytes = words[wi].as_bytes();
      let next_dist = curr_dist + 1;
      
      for i in 0..word_len {
        let mut pattern = [0u8; 6];
        unsafe {
          std::ptr::copy_nonoverlapping(bytes.as_ptr(), pattern.as_mut_ptr(), i);
          *pattern.get_unchecked_mut(i) = b'*';
          std::ptr::copy_nonoverlapping(bytes.as_ptr().add(i+1), pattern.as_mut_ptr().add(i+1), word_len-i-1);
        }
        
        if let Some(neighbors) = pattern_map.get(&pattern) {
          for &nei_idx in neighbors {
            if nei_idx == word_idx {
              continue;
            }
            
            let ni = nei_idx as usize;
            let d = unsafe { *dist.get_unchecked(ni) };
            
            if d > next_dist {
              unsafe { *dist.get_unchecked_mut(ni) = next_dist; }
              unsafe { parents.get_unchecked_mut(ni).push(word_idx); }
              queue.push_back(nei_idx);
            } else if d == next_dist {
              unsafe { parents.get_unchecked_mut(ni).push(word_idx); }
            }
          }
        }
      }
    }
    
    if unsafe { *dist.get_unchecked(end_idx) } == u16::MAX {
      return vec![];
    }
    
    // Backtrack
    let mut result = Vec::new();
    let mut path = Vec::with_capacity(unsafe { *dist.get_unchecked(end_idx) } as usize + 1);
    path.push(end_idx as u16);
    Self::backtrack_idx(begin_idx as u16, end_idx as u16, &parents, &mut path, &mut result);
    
    result.into_iter()
      .map(|path| path.into_iter().map(|idx| unsafe { words.get_unchecked(idx as usize).clone() }).collect())
      .collect()
  }
  
  fn backtrack_idx(
    begin_idx: u16,
    current: u16,
    parents: &[Vec<u16>],
    path: &mut Vec<u16>,
    result: &mut Vec<Vec<u16>>
  ) {
    if current == begin_idx {
      let mut reversed = path.clone();
      reversed.reverse();
      result.push(reversed);
      return;
    }
    
    for &parent_idx in &parents[current as usize] {
      path.push(parent_idx);
      Self::backtrack_idx(begin_idx, parent_idx, parents, path, result);
      path.pop();
    }
  }
}