class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0 # not in wordlist

        wordset = set(wordList)
        this_layer = [beginWord]
        visited = set([beginWord])
        distance = 0

        # BFS, thinking of layer
        while this_layer:
            distance += 1 # new bfs layer
            next_layer = []
            for each_word in this_layer:
                if each_word == endWord: # find ans
                    return distance

                for next_word in self.get_next_word(each_word, wordset):
                    if next_word in visited:
                        pass
                    else:
                        next_layer.append(next_word)
                        visited.add(next_word)

            this_layer = next_layer

        return 0 # not found

    def get_next_word(self, each_word, wordset): # find all possible case
        words = [] 
        for i, each_char in enumerate(each_word):
            left, right = each_word[:i], each_word[i+1:]
            for char in 'abcdefghijklmnopqrstuvwxyz':
                if each_word[i] == char:
                    continue
                else:
                    new_word = left + char + right
                    if new_word in wordset:
                        words.append(new_word)

        return words