interviewing.io
HARD
DATA STRUCTURES AND ALGORITHMS

How to Solve Transformation Dictionary

Written By
Adam Bhula

Transformation Dictionary Introduction

The Transformation Dictionary problem asks us to transform one word into another word by changing only a fixed number of characters at a time. This problem requires careful analysis of the dictionary of words, efficient traversal techniques (either bidirectional BFS with the use of sets or graph traversal), and consideration of the fixed number of character changes. This problem also requires consideration of real-world applications and transforming your solution into a functioning API for a given use case.

Transformation Dictionary Problem

Given a dictionary of words, determine whether it is possible to transform a given word into another with a fixed number of characters.

Follow-up Question #1:

How would you modify it to accept insertions/deletions of 1 character (accepting changing lengths of chars)?

Follow-up Question #2:

How would you modify this to be an api to handle a large amount of dictionary words but only a few checks for transforming?

Example Inputs and Outputs

Example 1

Input: start = 'dog', end = 'hat', dictionary = ['dot', 'cat', 'hot', 'hog', 'eat', 'dug', 'dig']
Output: True

Example 2

Input: start = 'abc', end = 'xyz', dictionary = ['abc', 'def', 'ghi']
Output: False

Example 3

Input: start = 'hit', end = 'cog', dictionary = ['hot', 'dot', 'dog', 'lot', 'log', 'cog']
Output: True

Transformation Dictionary Solutions

To begin it's important to note that this problem can be, and often is, solved by constructing a graph representation of the dictionary where each word is a node and there is an edge between two words if they differ by exactly one character. Wethen performs a breadth-first search (BFS) traversal from the start word, exploring its neighboring words until it reaches the end word or exhausts all possibilities. However for our solution we will opt for a more efficient approach today.

To solve this problem, we can use a bidirectional breadth-first search (BFS) approach. To better visualize our approach, imagine we are searching for a path from the start word to the end word (and also the reverse), considering each word in a dictionary as a potential step in the transformation process. We start by initializing our data structures.

We maintain two sets to keep track of the words visited from both the start and end points. Initially, the sets only contain the start and end words, respectively. We also have two queues, one for the start words and another for the end words, to perform the BFS from both ends simultaneously.

In each iteration, we choose a word from either the start queue or the end queue, alternating between them. We explore the neighbors of the chosen word by comparing it with each word in the dictionary. To compare two words for a one-character difference, we check if the words have the same length and count the number of differing characters between them. If the count is exactly 1, it means the words are neighbors in the transformation process.

If a neighbor is found to be one character away from the chosen word and has not been visited from the opposite end, we have discovered a valid step in the transformation path. We add the neighbor to the corresponding visited set and enqueue it into the respective queue for future exploration.

We continue this process, enqueuing newly discovered neighbors and updating the visited sets, until we either find a common word or both queues become empty, indicating that no transformation path exists. By exploring the search space from both ends, we can optimize the whole search process and improve overall efficiency.

We'll also have to deal with two extension questions that require us to modify our solution later on. Firstly let's take a look at our original solution below.

from collections import deque

def isTransformable(start, end, dictionary):
    if start == end:
        return True

    # Create sets to keep track of visited words from both ends
    visited_start = set([start])
    visited_end = set([end])

    # Create queues to perform BFS from both ends
    queue_start = deque([start])
    queue_end = deque([end])

    while queue_start and queue_end:
        # Perform BFS from the start word
        if len(queue_start) <= len(queue_end):
            word = queue_start.popleft()
            neighbors = getNeighbors(word, dictionary)

            for neighbor in neighbors:
                if neighbor in visited_end:
                    return True
                if neighbor not in visited_start:
                    visited_start.add(neighbor)
                    queue_start.append(neighbor)

        # Perform BFS from the end word
        else:
            word = queue_end.popleft()
            neighbors = getNeighbors(word, dictionary)

            for neighbor in neighbors:
                if neighbor in visited_start:
                    return True
                if neighbor not in visited_end:
                    visited_end.add(neighbor)
                    queue_end.append(neighbor)

    return False


def getNeighbors(word, dictionary):
    neighbors = []
    for neighbor in dictionary:
        if len(word) == len(neighbor):
            diff_count = sum(a != b for a, b in zip(word, neighbor))
            if diff_count == 1:
                neighbors.append(neighbor)
    return neighbors

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

print(isTransformable(start, end, dictionary))  # Output: True

Follow-up Question #1

How would you modify it to accept insertions/deletions of 1 character (accepting changing lengths of chars)?

To handle insertions and deletions, we can modify the code to generate all possible neighboring words by considering three cases: changing a character, inserting a character, and deleting a character. We can modify our getNeighbors function to handle the cases in which words are 1 character apart. If the two neighbours are 1 length difference and differ by one letter only then we can travel across those words. We should also adjust our function to be able to handle any number of character insertions/deletions by adjust the value 1 to any abritrary number.

from collections import deque

def isTransformable(start, end, dictionary):
    if start == end:
        return True

    # Create sets to keep track of visited words from both ends
    visited_start = set([start])
    visited_end = set([end])

    # Create queues to perform BFS from both ends
    queue_start = deque([start])
    queue_end = deque([end])

    while queue_start and queue_end:
        # Perform BFS from the start word
        if len(queue_start) <= len(queue_end):
            word = queue_start.popleft()
            neighbors = getNeighbors(word, dictionary)

            for neighbor in neighbors:
                if neighbor in visited_end:
                    return True
                if neighbor not in visited_start:
                    visited_start.add(neighbor)
                    queue_start.append(neighbor)

        # Perform BFS from the end word
        else:
            word = queue_end.popleft()
            neighbors = getNeighbors(word, dictionary)

            for neighbor in neighbors:
                if neighbor in visited_start:
                    return True
                if neighbor not in visited_end:
                    visited_end.add(neighbor)
                    queue_end.append(neighbor)

    return False


def getNeighbors(word, dictionary):
    neighbors = []
    for neighbor in dictionary:
        if len(word) == len(neighbor):
            diff_count = sum(a != b for a, b in zip(word, neighbor))
            if diff_count == 1:
                neighbors.append(neighbor)
        elif len(word) - len(neighbor) == 1:
            for i in range(len(word)):
                modified_word = word[:i] + word[i + 1:]
                if modified_word == neighbor:
                    neighbors.append(neighbor)
                    break
        elif len(neighbor) - len(word) == 1:
            for i in range(len(neighbor)):
                modified_word = neighbor[:i] + neighbor[i + 1:]
                if modified_word == word:
                    neighbors.append(neighbor)
                    break
    return neighbors


# Test case
start = 'dog'
end = 'seat'
dictionary = ['dot', 'cat', 'hot', 'hog', 'eat', 'dug', 'dig', 'hat']

result = isTransformable(start, end, dictionary)
print(result)

Follow-up Question #2

How would you modify this to be an api to handle a large amount of dictionary words but only a few checks for transforming?

To handle a large amount of dictionary words but only a few checks for transforming, we can design an API that preprocesses the dictionary and stores it in an efficient data structure, such as a trie or a hash table. This preprocessing step will ensure quick access to the dictionary words during the transformation checks.

For pre-processing we can:

  1. Create a data structure, such as a trie or a hash table, to store the dictionary words.
  2. Iterate through each word in the dictionary and add it to the data structure for efficient lookup.

We then expose an API function, let's say isTransformable, that takes the start word, end word, and the preprocessed data structure as input. Inside the isTransformable function, we can perform the transformation check using the existing logic from our previous solution. We then utilize the preprocessed data structure to quickly access dictionary words and check for neighbors during the transformation process.

Time/Space Complexity Analysis

  • Time Complexity: O(m * n), where m is the average length of the words and n is the number of words in the dictionary.
  • Space Complexity: O(m * n), where m is the average length of the words and n is the number of words in the dictionary.

About interviewing.io

interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.

We know exactly what to do and say to get the company, title, and salary you want.

Interview prep and job hunting are chaos and pain. We can help. Really.