幅優先探索 (BFS) で言葉の梯子のいちばん短い長さを求める

from collections import deque


def masks(w):
    for i in range(len(w)):
        a, b = w[:i], w[i + 1:]
        yield a + "*" + b


def take(box, w):
    out = []
    for k in masks(w):
        out += box.pop(k, [])
    return out


def ladder_length(
    begin, goal, words
):
    box = {}
    for w in words:
        for k in masks(w):
            if k not in box:
                box[k] = []
            box[k].append(w)
    dist = {begin: 1}
    queue = deque([begin])
    while queue:
        w = queue.popleft()
        if w == goal:
            return dist[w]
        d = dist[w] + 1
        for v in take(box, w):
            if v in dist:
                continue
            dist[v] = d
            queue.append(v)
    return 0

function masks(w) {
  const out = [];
  const n = w.length;
  for (let i = 0; i < n; i++) {
    const a = w.slice(0, i);
    const b = w.slice(i + 1);
    out.push(a + "*" + b);
  }
  return out;
}

function take(box, w) {
  const out = [];
  for (const k of masks(w)) {
    const g = box.get(k) || [];
    box.delete(k);
    out.push(...g);
  }
  return out;
}

function ladderLength(
  begin, goal, words
) {
  const box = new Map();
  for (const w of words) {
    for (const k of masks(w)) {
      if (!box.has(k)) {
        box.set(k, []);
      }
      box.get(k).push(w);
    }
  }
  const dist = new Map();
  dist.set(begin, 1);
  const queue = [begin];
  let head = 0;
  while (head < queue.length) {
    const w = queue[head];
    head++;
    if (w === goal) {
      return dist.get(w);
    }
    const d = dist.get(w) + 1;
    const next = take(box, w);
    for (const v of next) {
      if (dist.has(v)) continue;
      dist.set(v, d);
      queue.push(v);
    }
  }
  return 0;
}

func masks(w string) []string {
	out := []string{}
	for i := range w {
		k := w[:i] + "*" + w[i+1:]
		out = append(out, k)
	}
	return out
}

func take(
	box map[string][]string,
	w string,
) []string {
	out := []string{}
	for _, k := range masks(w) {
		out = append(out, box[k]...)
		delete(box, k)
	}
	return out
}

func ladderLength(
	begin, goal string,
	words []string,
) int {
	box := map[string][]string{}
	for _, w := range words {
		for _, k := range masks(w) {
			box[k] = append(box[k], w)
		}
	}
	dist := map[string]int{}
	dist[begin] = 1
	queue := []string{begin}
	head := 0
	for head < len(queue) {
		w := queue[head]
		head++
		if w == goal {
			return dist[w]
		}
		d := dist[w] + 1
		next := take(box, w)
		for _, v := range next {
			if _, ok := dist[v]; ok {
				continue
			}
			dist[v] = d
			queue = append(queue, v)
		}
	}
	return 0
}