Word Ladder — BFS
Today’s problem will be Word Ladder.
Alright first things first let’s discuss what this question is asking us for. We start with a beginWord and an endWord. We want to find the SHORTEST transformation sequence (other words, shortest path) from the beginWord to the endWord. The condition is that every step we take, we can only change one letter of each word, as well each ‘transition’ word must be included in our wordList.
We can think of the beginWord and the endWord as representing two nodes on a graph, the start node and the end node. The question is then asking if it possible to connect these two nodes by using intermediate nodes given to us by the wordList. These nodes will be connected by the condition that every neighboring node can only be different by one letter. The beginWord, endWord, and wordList can all be thought of as a undirected graph, where the words are the nodes and the edges between nodes differ by one letter. Now we are able to see more clearly how it is asking us for the shortest path, from start to end node. Normally to find the shortest path we can use a breadth first search approach.
The important part is assembling our graph, we need to find which words are going to be adjacent in the graph (ie. what words differ by one letter). We will replace each letter of a word with ‘*’ and then see if this intermediate state can be representing by a single letter change in the other words. For example, ‘cat’ -> ‘c*t’ <- ‘cot’. Both cat and cot can be represented by ‘c*t’ because there is only one letter that must be changed to step between these words. The three states for the word cat are: [‘*at’, ‘c*t’, ‘ca*’]. The map would be represented by:
‘*at’ ->[cat]
‘c*t’ ->[cat, cot]
‘ca*’ ->[cat]
We don't necessarily have to create this adjacency list but it saves us a lot of time later on. Without this step, we would later need to iterate over the entire word list and find words that differ by one letter. This optimizes are BFS function and allows us to group all words that map to a particular word state.
