Word Ladder - Get shortest ladder

Problem

Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only one letter at a time. The new word you get in each step must be in the dictionary.

Examples

Example 1

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

Output: ["hit","hot","dot","dog","cog"]

Explanation: There are 2 shortest transformation sequences, so returning any of them should be fine
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

Example 2

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: []
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

Intuition

The shortest transformation sequence can be found using BFS, as each transformation is a single step and we want the minimum number of steps. BFS explores all possible one-letter transformations level by level, ensuring the shortest path is found first.

Approach

Check if endWord is in the word list. If not, return an empty list.
Use a queue to perform BFS, starting from beginWord.
At each step, for the current word, generate all possible one-letter transformations.
If a transformation is in the word list and not visited, add it to the queue and mark as visited.
Track the path for each word.
Stop when endWord is reached and return the path.
If the queue is empty and endWord is not reached, return an empty list.

Code

C++

class Solution {
public:
  vector<string> findLadder(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> dict(wordList.begin(), wordList.end());
    if (!dict.count(endWord)) return {};
    queue<vector<string>> q;
    q.push({beginWord});
    unordered_set<string> visited;
    while (!q.empty()) {
      int sz = q.size();
      unordered_set<string> levelVisited;
      for (int i = 0; i < sz; ++i) {
        auto path = q.front(); q.pop();
        string last = path.back();
        if (last == endWord) return path;
        for (int j = 0; j < last.size(); ++j) {
          string tmp = last;
          for (char c = 'a'; c <= 'z'; ++c) {
            tmp[j] = c;
            if (dict.count(tmp) && !visited.count(tmp)) {
              auto newPath = path;
              newPath.push_back(tmp);
              q.push(newPath);
              levelVisited.insert(tmp);
            }
          }
        }
      }
      for (auto& w : levelVisited) visited.insert(w);
    }
    return {};
  }
};

Go

func findLadder(beginWord string, endWord string, wordList []string) []string {
  dict := make(map[string]bool)
  for _, w := range wordList {
    dict[w] = true
  }
  if !dict[endWord] {
    return []string{}
  }
  type pathType []string
  q := []pathType{{beginWord}}
  visited := make(map[string]bool)
  for len(q) > 0 {
    sz := len(q)
    levelVisited := make(map[string]bool)
    for i := 0; i < sz; i++ {
      path := q[0]
      q = q[1:]
      last := path[len(path)-1]
      if last == endWord {
        return path
      }
      for j := 0; j < len(last); j++ {
        for c := 'a'; c <= 'z'; c++ {
          tmp := []rune(last)
          tmp[j] = c
          nw := string(tmp)
          if dict[nw] && !visited[nw] {
            newPath := append([]string{}, path...)
            newPath = append(newPath, nw)
            q = append(q, newPath)
            levelVisited[nw] = true
          }
        }
      }
    }
    for w := range levelVisited {
      visited[w] = true
    }
  }
  return []string{}
}

Java

class Solution {
  public List<String> findLadder(String beginWord, String endWord, List<String> wordList) {
    Set<String> dict = new HashSet<>(wordList);
    if (!dict.contains(endWord)) return new ArrayList<>();
    Queue<List<String>> q = new LinkedList<>();
    q.offer(Arrays.asList(beginWord));
    Set<String> visited = new HashSet<>();
    while (!q.isEmpty()) {
      int sz = q.size();
      Set<String> levelVisited = new HashSet<>();
      for (int i = 0; i < sz; i++) {
        List<String> path = q.poll();
        String last = path.get(path.size() - 1);
        if (last.equals(endWord)) return path;
        char[] arr = last.toCharArray();
        for (int j = 0; j < arr.length; j++) {
          char orig = arr[j];
          for (char c = 'a'; c <= 'z'; c++) {
            arr[j] = c;
            String nw = new String(arr);
            if (dict.contains(nw) && !visited.contains(nw)) {
              List<String> newPath = new ArrayList<>(path);
              newPath.add(nw);
              q.offer(newPath);
              levelVisited.add(nw);
            }
          }
          arr[j] = orig;
        }
      }
      visited.addAll(levelVisited);
    }
    return new ArrayList<>();
  }
}

Kotlin

class Solution {
  fun findLadder(beginWord: String, endWord: String, wordList: List<String>): List<String> {
    val dict = wordList.toHashSet()
    if (endWord !in dict) return emptyList()
    val q = ArrayDeque<List<String>>()
    q.add(listOf(beginWord))
    val visited = mutableSetOf<String>()
    while (q.isNotEmpty()) {
      val sz = q.size
      val levelVisited = mutableSetOf<String>()
      repeat(sz) {
        val path = q.removeFirst()
        val last = path.last()
        if (last == endWord) return path
        for (i in last.indices) {
          for (c in 'a'..'z') {
            val nw = last.substring(0, i) + c + last.substring(i + 1)
            if (nw in dict && nw !in visited) {
              q.add(path + nw)
              levelVisited.add(nw)
            }
          }
        }
      }
      visited.addAll(levelVisited)
    }
    return emptyList()
  }
}

Python

class Solution:
  def findLadder(self, beginWord: str, endWord: str, wordList: list[str]) -> list[str]:
    word_set: set[str] = set(wordList)
    if endWord not in word_set:
      return []
    from collections import deque
    q: deque[list[str]] = deque([[beginWord]])
    visited: set[str] = set()
    while q:
      sz = len(q)
      level_visited: set[str] = set()
      for _ in range(sz):
        path = q.popleft()
        last = path[-1]
        if last == endWord:
          return path
        for i in range(len(last)):
          for c in 'abcdefghijklmnopqrstuvwxyz':
            nw = last[:i] + c + last[i+1:]
            if nw in word_set and nw not in visited:
              q.append(path + [nw])
              level_visited.add(nw)
      visited.update(level_visited)
    return []

Rust

impl Solution {
  pub fn find_ladder(begin_word: String, end_word: String, word_list: Vec<String>) -> Vec<String> {
    use std::collections::{HashSet, VecDeque};
    let dict: HashSet<_> = word_list.into_iter().collect();
    if !dict.contains(&end_word) { return vec![]; }
    let mut q = VecDeque::new();
    q.push_back(vec![begin_word.clone()]);
    let mut visited = HashSet::new();
    while !q.is_empty() {
      let sz = q.len();
      let mut level_visited = HashSet::new();
      for _ in 0..sz {
        let path = q.pop_front().unwrap();
        let last = path.last().unwrap();
        if last == &end_word { return path; }
        let mut arr: Vec<char> = last.chars().collect();
        for i in 0..arr.len() {
          let orig = arr[i];
          for c in 'a'..='z' {
            arr[i] = c;
            let nw: String = arr.iter().collect();
            if dict.contains(&nw) && !visited.contains(&nw) {
              let mut new_path = path.clone();
              new_path.push(nw.clone());
              q.push_back(new_path);
              level_visited.insert(nw);
            }
          }
          arr[i] = orig;
        }
      }
      visited.extend(level_visited);
    }
    vec![]
  }
}

Complexity

⏰ Time complexity: O(N * L^2) where N is the number of words and L is the length of each word.
🧺 Space complexity: O(N * L) for the queue and visited sets.