A "word ladder" consists of a sequence of words, all of the same length, each successive word differing from the previous by only one letter. By changing only one letter at a time, the first word can be transformed into the last word.
For example, TAR can be converted to PIT in the following manner:
TAR -> PAR -> PAT -> PITWrite a program word_ladder.py that solves Word Ladder problems by identifying a sequence of words that will lead from a given initial word to a given final word.
Strategy:
Create a graph of all the possible words, where edges connect words (vertices) that different from each other by only one letter. (So, TAR will be connected to TAT, TAP, TAB, TAD, etc.)
Beginning at the given word, perform a Breadth-First Search of the graph beginning at our initial word. Search through the graph using the BFS algorithm until we arrive at the final word.
Implementing this strategy will require modifying the Vertex class so that we can identify previous nodes and identify nodes that have already been visited. See development in the class notes and the book for information on how to do this.