transformation_dictionary.py

"""
problem from https://www.youtube.com/watch?v=nY9tgnWLsTk

isTransformable(start: string, end: string, dictionary:string[]): boolean
start = 'dog'
end = 'hat'

dictionary = ['dot', 'cat', 'hot', 'hog', 'eat', 'dug', 'dig']
dog -> dot -> hot -> hat
"""

# helper function
def path_exists(dictionary: [str], i: int, j: int) -> bool:
    word_1 = dictionary[i]
    word_2 = dictionary[j]
    
    different_letters = 0
    for c_1, c_2 in zip(word_1, word_2):
        if c_1 != c_2:
            different_letters += 1

    return different_letters == 1

def is_transformable(start: str, end: str, dictionary: [str]) -> bool: 
    # step one: find adjacent words, make an adjacency list
    # initialization,
    dictionary.extend([start, end])
    length = len(dictionary)
    adjacency_list = [[False for _ in range(length)] for _ in range(length)]
    
    for i in range(length):
        for j in range(length):
            if i == j:
                pass
            adjacency_list[i][j] = path_exists(dictionary, i, j)
    
    start_index = dictionary.index(start)
    end_index = dictionary.index(end)

    # need to keep track of which nodes we have visited
    visited = [start_index]

    # just do a DFS to find if a path exists
    def can_i_get_there(adjacency_list, visited, end_index):
        # visit every node that we haven't yet visited
        amount_of_nodes = len(adjacency_list)
        # grab the last node
        last_visited_node = visited[-1]

        for i in range(amount_of_nodes):
            if i in visited:
                continue
            if adjacency_list[last_visited_node][i]:
                return True
            
            # now we visit i and recurse
            new_visited = visited.copy()
            new_visited.append(i)
            if can_i_get_there(adjacency_list, new_visited, end_index):
                return True

        return False

    return can_i_get_there(adjacency_list, visited, end_index)




start = 'dog'
end = 'hat'
dictionary = ['dot', 'cat', 'hot', 'hog', 'eat', 'dug', 'dig']
print(is_transformable(start, end, dictionary))