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.
Return the number of words in the shortest such chain, counting both beginWord and endWord. If no chain exists, return 0.
cat → cot → cog → dog changes one letter per step and uses 4 words. cat and dog differ in all three letters, so no chain can be shorter.
lamp → lame → lime would work, but lime is not in the dictionary, so it can't be the last word.
tan is in the dictionary, but nothing connects to it: red and rod differ from tad and tan in at least two letters.
Constraints
1 <= beginWord.length <= 10endWord.length == beginWord.length1 <= wordList.length <= 5000wordList[i].length == beginWord.lengthbeginWord, endWord and every wordList[i] are made of lowercase English letters.beginWord != endWordwordList are all different.Treat each word as a node, with an edge between two words that differ in exactly one letter. The shortest chain is a shortest path in an unweighted graph, so search breadth-first from beginWord.
4