You are given two words, beginWord and endWord, and a dictionary of words called wordList. Your task is to find all the shortest transformation sequences from beginWord to endWord, such that:

1. Only one letter can be changed at a time.

2. Each transformed word must exist in the given wordList.

3. The transformation sequence must begin with beginWord and end with endWord.

Return all the shortest transformation sequences as a list of lists. If no valid transformation exists, return an empty list.

Constraints:

• $1 \leq$ beginWord.length $\leq 5$

• endWord.length == beginWord.length

• $1 \leq$ wordList.length $\leq 500$

• wordList[i].length == beginWord.length

• beginWord, endWord, and wordList[i] consist of lowercase English letters.

• beginWord != endWord

• All the words in wordList are unique.

• The sum of all shortest transformation sequences does not exceed $10^5$.

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.