Graph BFS / DFS
LC #127Hard
Word Ladder
Graph BFS / DFS
AmazonGoogleMetaBloombergProblem
Transform beginWord into endWord by changing one letter at a time, using only words from wordList. Find the shortest transformation sequence length.
bfsgraphstring
Constraints
- ›1 ≤ beginWord.length ≤ 10
- ›beginWord, endWord, wordList[i] all same length
- ›All lowercase English letters
- ›beginWord ≠ endWord
Example
Input
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]Output
5Why
"hit"→"hot"→"dot"→"dog"→"cog" — 5 words, 4 transformations