Edit distance
Hard
Determine the Edit Distance in a Word Ladder: Given two words (beginWord and endWord), and a dictionary's word list, find the minimum number of operations needed to change beginWord into endWord.
You can change only one letter at a time, and each intermediate word must exist in the word list. If there is no possible transformation, return None (Python), -1 (Java & C++), null (Javascript).
Examples
beginWord = 'hit' endWord = 'cog' wordList = ["hit", "hot", "dot", "dog", "cog"] output: 4 # hit -> hot -> dot -> dog -> cog beginWord = 'word' endWord = 'word' wordList = ['word', 'ward'] output: 0 beginWord = 'hit' endWord = 'cog' wordList = ["hit", "hot", "dot", "dog"] output: None # because no 'cog' in list
Our solution tackles the problem by first constructing a graph that represents all possible transformations between words in the list, where an edge exists between two words if they differ by exactly one character (i.e., they are "one edit distance" apart). This is done by iterating over the list of words and comparing each pair to determine if they meet the one edit distance condition. If they do, an edge is added between them in the graph.
After constructing the graph, we use a breadth-first search (BFS) approach to find the shortest path from the start_word to the end_word. We initiate a queue that starts with the start_word and its associated edit distance (initially 0). As we traverse the graph, for each word, we check if it's the end_word. If so, we return the current edit distance incremented by one. If not, we add the word's neighbors to the queue for further exploration, ensuring that we don't revisit previously seen words.
The BFS guarantees that the first time we reach the end_word, it is via the shortest path, and we can stop the search early.
Time Complexity: The time complexity of the solution is O(n^2 * m), where n is the number of words and m is the length of each word. This complexity arises from the double loop that compares each word to every other word (O(n^2)), and for each comparison, we check if the words differ by exactly one character (O(m)).
Space Complexity: The space complexity is O(n^2), where n is the number of words. This space is required to store the graph, where each word can potentially have edges to all other words. Additionally, the BFS queue and the visited set require O(n) space in the worst case.
In this video, Thomas, Google SWE, answers the Edit Distance coding interview question.
Interview experiences
2 sharedRelated courses
