Word Ladder 2 Implementation

HardPython

Problem

OfferUp may need to find the shortest sequence of valid keyword transformations between two search terms. Given a beginWord, an endWord, and a dictionary, return every shortest transformation sequence.

A transformation changes exactly one character, and every intermediate word must appear in wordList. The first and last words are included in each returned sequence. If no transformation exists, return an empty list.

Formal Specification

Implement find_ladders(beginWord, endWord, wordList).

beginWord: a lowercase string.
endWord: a lowercase string with the same length as beginWord.
wordList: a list of lowercase strings of the same length.
Return a list of paths, where each path is a list of strings from beginWord to endWord.
Return only paths with the minimum possible number of transformations. The paths may be returned in any order.

Use an efficient representation for finding words that differ at exactly one position. A path cannot reuse a word.

Constraints

1 <= len(beginWord) <= 10
len(beginWord) == len(endWord)
1 <= len(wordList) <= 5 * 10^3
All words contain lowercase English letters.
All words have the same length.
Duplicate dictionary entries may be present.

Function Signature

def find_ladders(beginWord, endWord, wordList):

Formal Specification

Implement find_ladders(beginWord, endWord, wordList).

beginWord: a lowercase string.
endWord: a lowercase string with the same length as beginWord.
wordList: a list of lowercase strings of the same length.
Return a list of paths, where each path is a list of strings from beginWord to endWord.
Return only paths with the minimum possible number of transformations. The paths may be returned in any order.

Use an efficient representation for finding words that differ at exactly one position. A path cannot reuse a word.