Given two strings (Word 1 and Word 2) and a list of valid words from a dictionary, return the minimum number of operations required to convert Word 1 to Word 2.
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.
Related questions
Given a list of transactions between friends, return the minimum number of transactions required to settle the debts. For e.g. Alice gave $5 to Bob and Bob gave $5 to Bill. Answer will be 1.Given a list of strings, find the number of occurrences of the second letter of the first word, and return the character and its count.Calculate the minimum number of turns required to open a lock.Related courses
