Shortest word transformation

from collections import deque
from string import ascii_lowercase

def ladder_length(begin_word, end_word, word_list):
    words = set(word_list)
    if end_word not in words:
        return 0
    words.discard(begin_word)
    q = deque([(begin_word, 1)])          # (word, words in the ladder so far)
    while q:
        word, length = q.popleft()
        if word == end_word:
            return length
        for i in range(len(word)):        # neighbours: change one position
            for ch in ascii_lowercase:
                cand = word[:i] + ch + word[i + 1:]
                if cand in words:
                    words.remove(cand)    # removing it marks it visited
                    q.append((cand, length + 1))
    return 0

#include <queue>
#include <string>
#include <unordered_set>
#include <utility>
#include <vector>

int solve(std::string beginWord, std::string endWord, const std::vector<std::string>& wordList) {
    std::unordered_set<std::string> words(wordList.begin(), wordList.end());
    if (!words.count(endWord)) return 0;
    words.erase(beginWord);
    std::queue<std::pair<std::string, int>> q;          // (word, words in the ladder so far)
    q.push({beginWord, 1});
    while (!q.empty()) {
        auto [word, length] = q.front();
        q.pop();
        if (word == endWord) return length;
        for (size_t i = 0; i < word.size(); ++i) {
            std::string cand = word;
            for (char ch = 'a'; ch <= 'z'; ++ch) {          // change position i
                cand[i] = ch;
                if (words.erase(cand)) q.push({cand, length + 1});   // erase marks it visited
            }
        }
    }
    return 0;
}

import java.util.*;

class Solution {
    public int ladderLength(String beginWord, String endWord, String[] wordList) {
        Set<String> words = new HashSet<>(Arrays.asList(wordList));
        if (!words.contains(endWord)) return 0;
        words.remove(beginWord);
        ArrayDeque<String> q = new ArrayDeque<>();
        q.add(beginWord);
        for (int length = 1; !q.isEmpty(); length++) {       // one level per ladder length
            for (int k = q.size(); k > 0; k--) {
                String word = q.poll();
                if (word.equals(endWord)) return length;
                char[] cand = word.toCharArray();
                for (int i = 0; i < cand.length; i++) {
                    char keep = cand[i];
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        cand[i] = ch;
                        String s = new String(cand);
                        if (words.remove(s)) q.add(s);       // remove marks it visited
                    }
                    cand[i] = keep;
                }
            }
        }
        return 0;
    }
}

function ladderLength(beginWord, endWord, wordList) {
  const words = new Set(wordList);
  if (!words.has(endWord)) return 0;
  words.delete(beginWord);
  const q = [[beginWord, 1]];               // [word, words in the ladder so far]
  for (let head = 0; head < q.length; head++) {
    const [word, length] = q[head];
    if (word === endWord) return length;
    for (let i = 0; i < word.length; i++) {
      for (let code = 97; code <= 122; code++) {   // a..z at position i
        const cand = word.slice(0, i) + String.fromCharCode(code) + word.slice(i + 1);
        if (words.has(cand)) { words.delete(cand); q.push([cand, length + 1]); }
      }
    }
  }
  return 0;
}

use std::collections::{HashSet, VecDeque};

fn solve(begin_word: &str, end_word: &str, word_list: &[&str]) -> i64 {
    let mut words: HashSet<String> = word_list.iter().map(|w| w.to_string()).collect();
    if !words.contains(end_word) {
        return 0;
    }
    words.remove(begin_word);
    let mut q = VecDeque::from([(begin_word.to_string(), 1i64)]);   // (word, ladder length)
    while let Some((word, length)) = q.pop_front() {
        if word == end_word {
            return length;
        }
        let mut cand: Vec<u8> = word.into_bytes();
        for i in 0..cand.len() {
            let keep = cand[i];
            for ch in b'a'..=b'z' {
                cand[i] = ch;
                let s = String::from_utf8(cand.clone()).unwrap();
                if words.remove(&s) {                    // remove marks it visited
                    q.push_back((s, length + 1));
                }
            }
            cand[i] = keep;
        }
    }
    0
}

import qualified Data.Set as S
import Data.Sequence (Seq (..), (|>))
import qualified Data.Sequence as Q

solve :: String -> String -> [String] -> Int
solve begin end list
  | not (S.member end dict) = 0
  | otherwise = bfs (Q.singleton (begin, 1)) (S.delete begin dict)
  where
    dict = S.fromList list
    -- the set holds the words not yet reached; taking a word out marks it visited
    bfs Empty _ = 0
    bfs ((w, len) :<| q) left
      | w == end = len
      | otherwise =
          let cands = [take i w ++ [ch] ++ drop (i + 1) w | i <- [0 .. length w - 1], ch <- ['a' .. 'z']]
              fresh = S.toList (S.fromList (filter (`S.member` left) cands))
          in bfs (foldl (|>) q [(c, len + 1) | c <- fresh]) (foldr S.delete left fresh)