You want to turn the word beginWord into the word endWord by changing one letter at a time. Every word you step onto after beginWord must be in the dictionary wordList, including endWord itself. beginWord does not need to be in wordList.
A chain is the list of words from beginWord to endWord, both included. Return every chain of the shortest possible length, each as a list of words in the order they are visited. You may return the chains in any order. If no chain exists, return an empty list.
bag and dot differ in all three letters, so every chain needs at least three steps, and exactly three routes manage it. rag is one letter from bag but leads nowhere, so it is in no chain.
sun → fun → fin → fan also works, but it is a step longer than sun → fun → fan, so it is left out.
[]
fan is not in the dictionary, so no chain can end there.
Constraints
1 <= beginWord.length <= 5endWord.length == beginWord.length1 <= wordList.length <= 500wordList[i].length == beginWord.lengthbeginWord, endWord and every wordList[i] are made of lowercase English letters.beginWord != endWordwordList are all different.2 × 10⁴ words (count every word of every chain).Join words that are one letter apart: the shortest chains are the shortest paths from beginWord, so a breadth-first search finds their length. But don't carry whole chains through the search. Partial chains can multiply enormously even when only a few ever reach endWord.