gistfile1.py

import heapq
import itertools

def _insert(dic, c):
    try:
        return dic[c]
    except KeyError:
        dic[c] = {}
        return dic[c]

def build_trie(items):
    res = {}
    for item in items:
        pos = res
        for c in list(item) + ["__end__"]:
            pos = _insert(pos, c)
    return res

def _get_branch(dic, prefix):
    if len(prefix) == 0:
        return dic
    first, rest = prefix[0], prefix[1:]
    try:
        return _get_branch(dic[first], rest)
    except KeyError:
        return {}

def _exists(dic, word):
    return '__end__' in _get_branch(dic, word)

def _edit(start, end):
    s = set()
    c = 0
    for idx, (c1, c2) in enumerate(zip(start, end)):
        if c1 != c2:
            c += 1
            s.add(idx)
    return c, s

def perform_algo(start, end, trie):
    seen = {start}
    q = [(_edit(start, end)[0], (0, _edit(start, end)[1], start))]
    while len(q) > 0:

        # Unpack data
        edit_distance, (n_changes_made, indices_to_change, word) = heapq.heappop(q)

        # If edit distance if <= 1 return the number of changes + those to do
        if edit_distance <= 1:
            return n_changes_made + edit_distance

        for idx in indices_to_change:
            # get root up till idx
            for char in _get_branch(trie, word[:idx]).keys():
                if char != '__end__':
                    # compose word changing character
                    composed_word = word[:idx] + char + word[idx+1:]

                    # if word exists and has a <= edit distance, add to queue
                    if _exists(trie, composed_word) and composed_word not in seen:
                        seen.add(word)
                        new_edit_distance, new_indices_to_change = _edit(composed_word, end)
                        if new_edit_distance <= edit_distance:
                            heapq.heappush(q, (new_edit_distance, (n_changes_made + 1, new_indices_to_change, composed_word)))
    return False