Show problems as
Classic problem #126HardHash TableStringBacktrackingBreadth-First SearchBidirectional Search

Word Ladder II

Real-world version: Call Sign Relay Routes
Tracked in this browser only
Read Word Ladder II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A relay station has to move from the call sign beginWord to the call sign endWord. All call signs are lowercase strings of the same length.

One hop rewrites exactly one letter of the current sign, and the sign it produces has to appear in the approved register wordList. A route is a list of signs that starts with beginWord, ends with endWord, and where each sign after the first is one hop from the sign before it. beginWord itself does not have to be in the register.

Return every route that uses the fewest hops possible, each route listed from beginWord to endWord. The routes themselves may come back in any order. Return an empty list when no route exists at all.

Examples

Example 1

Input
beginWord = "fin", endWord = "ban", wordList = ["fan","fun","ban","bin","bun"]
Output
[["fin","bin","ban"],["fin","fan","ban"]]

Two routes of two hops each are the shortest ones: `fin` to `bin` to `ban`, and `fin` to `fan` to `ban`. Every sign in them comes from the register and every hop rewrites exactly one letter.

Example 2

Input
beginWord = "tin", endWord = "ten", wordList = ["ten","tan"]
Output
[["tin","ten"]]

`ten` is in the register and differs from `tin` in one letter, so a single hop is enough and only one route is that short.

Example 3

Input
beginWord = "fin", endWord = "oak", wordList = ["fan","ban","oak"]
Output
[]

`oak` is in the register but shares no letter position with any sign that can be reached from `fin`, so no route ever arrives and the answer is empty.

Constraints

  • 1 <= beginWord.length <= 5
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 500
  • wordList[i].length == beginWord.length
  • beginWord, endWord and every wordList[i] hold lowercase English letters only.
  • beginWord != endWord
  • The register holds no repeated call sign.
  • The shortest routes hold at most 10^5 signs in total.

The values you return may be in any order.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def find_ladders(beginWord: str, endWord: str, wordList: list[str]) -> list[list[str]]:
Java
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList)

More on the same topics