Method ladderLength

BFS/WordLadder.py:56–87

:type beginWord: str :type endWord: str :type wordList: List[str] :rtype: int

(self, beginWord, endWord, wordList)

from collections import deque
class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        
        if len(beginWord) == 1:
            return 2
        
        _wordList = set(wordList)
        
        result = deque([[beginWord, 1]])

        while result:
            word, length = result.popleft()
            
            if word == endWord:
                return length 

            _length = length + 1

            for i in range(len(word)):
                for c in 'qwertyuiopasdfghjklzxcvbnm':
                    new = word[:i]+c+word[i+1:]
                    
                    if new in _wordList:
                        _wordList.remove(new)
                        result.append([new, _length])
        
        return 0