← Back to index
HardPython4 min read

Word Ladder

find shortest transformation sequence from beginWord to endWord using bfs.

bfsgraphstring

Problem link

View on LeetCode

Solutions in this repo

  • Python../word-ladder/solution.pyPython solution

use bfs to find shortest path. start from beginWord, try changing each character to all possible letters, check if result is in word list and not visited.

use queue for level-order traversal. track level to count transformations. early return when endWord is found.

optimization

convert word list to set for O(1) lookup. try all 26 letters for each position. use visited set to avoid cycles.

complexity

O(m * n * 26) time where m is word length and n is word list size. O(n) space for queue and visited set.