#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
static int cmpStr(const void *a, const void *b) {
return strcmp(*(char *const *)a, *(char *const *)b);
}
// index of w in the sorted dictionary, or -1
static int lookup(char **sorted, int n, const char *w) {
char **hit = bsearch(&w, sorted, n, sizeof(char *), cmpStr);
return hit ? (int)(hit - sorted) : -1;
}
int ladderLength(char *beginWord, char *endWord, char **wordList,
int wordListSize) {
// C has no hash set: sort the words and binary-search them instead,
// with a parallel flag array standing in for erase()
int n = wordListSize, len = strlen(beginWord);
char **words = malloc(n * sizeof(char *));
memcpy(words, wordList, n * sizeof(char *));
qsort(words, n, sizeof(char *), cmpStr);
bool *removed = calloc(n, sizeof(bool));
int result = 0;
if (lookup(words, n, endWord) < 0)
goto done;
// each word is enqueued at most once, plus beginWord
char **q = malloc((n + 1) * sizeof(char *));
int head = 0, tail = 0;
q[tail++] = beginWord;
int b = lookup(words, n, beginWord);
if (b >= 0)
removed[b] = true;
int length = 1;
char *w = malloc(len + 1);
while (head < tail) {
int levelEnd = tail;
while (head < levelEnd) {
strcpy(w, q[head++]);
for (int pos = 0; pos < len; pos++) {
char original = w[pos];
for (char c = 'a'; c <= 'z'; c++) {
if (c == original)
continue;
w[pos] = c;
if (strcmp(w, endWord) == 0) {
result = length + 1;
goto cleanup;
}
int k = lookup(words, n, w);
if (k >= 0 && !removed[k]) {
removed[k] = true;
q[tail++] = words[k];
}
}
w[pos] = original;
}
}
length++;
}
cleanup:
free(w);
free(q);
done:
free(removed);
free(words);
return result;
}
#include <queue>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string> &wordList) {
unordered_set<string> words(wordList.begin(), wordList.end());
if (!words.count(endWord))
return 0;
queue<string> q;
q.push(beginWord);
words.erase(beginWord);
int length = 1;
while (!q.empty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
string w = q.front();
q.pop();
for (int pos = 0; pos < w.size(); pos++) {
char original = w[pos];
for (char c = 'a'; c <= 'z'; c++) {
if (c == original)
continue;
w[pos] = c;
if (w == endWord)
return length + 1;
if (words.count(w)) {
words.erase(w);
q.push(w);
}
}
w[pos] = original;
}
}
length++;
}
return 0;
}
};
package graphs
func ladderLength(beginWord string, endWord string, wordList []string) int {
words := make(map[string]bool, len(wordList))
for _, w := range wordList {
words[w] = true
}
if !words[endWord] {
return 0
}
q := []string{beginWord}
delete(words, beginWord)
length := 1
for len(q) > 0 {
sz := len(q)
for i := 0; i < sz; i++ {
w := []byte(q[0])
q = q[1:]
for pos := range w {
original := w[pos]
for c := byte('a'); c <= 'z'; c++ {
if c == original {
continue
}
w[pos] = c
s := string(w)
if s == endWord {
return length + 1
}
if words[s] {
delete(words, s)
q = append(q, s)
}
}
w[pos] = original
}
}
length++
}
return 0
}
import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.Set;
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> words = new HashSet<>(wordList);
if (!words.contains(endWord))
return 0;
Queue<String> q = new ArrayDeque<>();
q.offer(beginWord);
words.remove(beginWord);
int length = 1;
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
char[] w = q.poll().toCharArray();
for (int pos = 0; pos < w.length; pos++) {
char original = w[pos];
for (char c = 'a'; c <= 'z'; c++) {
if (c == original)
continue;
w[pos] = c;
String s = new String(w);
if (s.equals(endWord))
return length + 1;
if (words.remove(s))
q.offer(s);
}
w[pos] = original;
}
}
length++;
}
return 0;
}
}
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
var ladderLength = function (beginWord, endWord, wordList) {
const words = new Set(wordList);
if (!words.has(endWord)) return 0;
let q = [beginWord];
words.delete(beginWord);
let length = 1;
while (q.length > 0) {
// swap in a fresh array per level: Array.shift() is O(n)
const next = [];
for (const word of q) {
const w = word.split("");
for (let pos = 0; pos < w.length; pos++) {
const original = w[pos];
for (let code = 97; code <= 122; code++) {
const c = String.fromCharCode(code);
if (c === original) continue;
w[pos] = c;
const s = w.join("");
if (s === endWord) return length + 1;
if (words.delete(s)) next.push(s);
}
w[pos] = original;
}
}
q = next;
length++;
}
return 0;
};
from collections import deque
from string import ascii_lowercase
from typing import List
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
words = set(wordList)
if endWord not in words:
return 0
q = deque([beginWord])
words.discard(beginWord)
length = 1
while q:
for _ in range(len(q)):
w = list(q.popleft())
for pos in range(len(w)):
original = w[pos]
for c in ascii_lowercase:
if c == original:
continue
w[pos] = c
s = "".join(w)
if s == endWord:
return length + 1
if s in words:
words.remove(s)
q.append(s)
w[pos] = original
length += 1
return 0
use std::collections::{HashSet, VecDeque};
impl Solution {
pub fn ladder_length(begin_word: String, end_word: String, word_list: Vec<String>) -> i32 {
let mut words: HashSet<Vec<u8>> = word_list.into_iter().map(String::into_bytes).collect();
let end = end_word.into_bytes();
if !words.contains(&end) {
return 0;
}
let begin = begin_word.into_bytes();
words.remove(&begin);
let mut q = VecDeque::from([begin]);
let mut length = 1;
while !q.is_empty() {
for _ in 0..q.len() {
let mut w = q.pop_front().unwrap();
for pos in 0..w.len() {
let original = w[pos];
for c in b'a'..=b'z' {
if c == original {
continue;
}
w[pos] = c;
if w == end {
return length + 1;
}
if words.remove(&w) {
q.push_back(w.clone());
}
}
w[pos] = original;
}
}
length += 1;
}
0
}
}