want to reach from start to end by modifying one character at a time and making sure each resulting word is also in the dictionary

dictionary_nomad.py

from itertools import combinations
from collections import deque


def is_nbr(s1, s2):
    if len(s1) != len(s2):
        return False

    dist = (int(a != b) for a,b in zip(s1, s2))

    return sum(dist) == 1


def make_graph(words, n):
    adj_list = [[] for _ in range(n)]
    for i,j in combinations(range(n), 2):
        if is_nbr(words[i], words[j]):
            adj_list[i].append(j)
            adj_list[j].append(i)
    return adj_list

def find_steps(dictionary, start, end):
    if len(start) != len(end):
            return -1
    if start == end:
        return 0

    words = dictionary + [start, end]
    n = len(words)
    source = n - 2
    dest = n - 1
    adj_list = make_graph(words, n)

    queue = deque()
    queue.append((source, 0))
    visited = set()

    while len(queue):
        v, d = queue.popleft()
        if v == dest:
            return d

        visited.add(v)

        for u in adj_list[v]:
            if u not in visited:
                queue.append((u, d + 1))

    return -1



############


def gen_nbr(s):
    for i in range(len(s)):
        for c in range(97, 97 + 26):
            yield s[:i] + chr(c) + s[i + 1 :]

# use this if dictionary is too large, bfs might need optimisation like bidi search or best first
# generates neighbors on the fly, might be less work as only one char changed, and time saved in creating adj list
def find_steps1(dictionary, start, end):
    if len(start) != len(end):
            return -1
    if start == end:
        return 0

    words = set(dictionary)
    queue = deque()
    queue.append((start, 0))
    visited = set()
    visited.add(start)

    while len(queue):
        v, d = queue.popleft()
        if v == end:
            return d

        for u in gen_nbr(v):
            if u not in visited and u in words:
                queue.append((u, d + 1))
                visited.add(u)

    return -1


is_nbr("say", "soy")

find_steps(["day", "soy"], "soy", "day")

find_steps(["day", "soy", "say"], "soy", "day")