My 12 lines Python code for word ladder


  • 1
    J
    def ladderLength(beginWord, endWord, wordList):
        
        wordList.append(endWord)
        queue = collections.deque([[beginWord, 1]])
        leng = len(beginWord)
        
        while queue:
            word, length = queue.popleft()
            if word == endWord:
                return length
            for n in wordList:
                if sum(n[i]!=word[i] for i in xrange(leng))==1:
                    wordList.remove(n)
                    queue.append([n,length+1])
        return 0
    

  • 1
    M

    Sadly, this solution doesn't work anymore. The test case for this problem are a mess, but it fails on this test set:

    "hot", "dog", ["hot","dog","cog","pot","dot"]

    Returns 4 instead of 3

    I modified the code a little to account for the broken test data:

    class Solution(object):
        def ladderLength(self, beginWord, endWord, wordList):
            """
            :type beginWord: str
            :type endWord: str
            :type wordList: List[str]
            :rtype: int
            """
            if beginWord in wordList:
                wordList.remove(beginWord)
            
            if endWord not in wordList:
                return 0
            
            wordList.append(endWord)
            queue = collections.deque([[beginWord, 1]])
            leng = len(beginWord)
        
            while queue:
                word, length = queue.popleft()
                if word == endWord:
                    return length
                for n in wordList:
                    if sum(n[i] != word[i] for i in xrange(leng)) == 1:
                        wordList.remove(n)
                        queue.append([n,length+1])
            return 0        
    

  • 1
    M

    I scratched my head for a long time, but I finally found the bug in your code: you're mutating wordList while you're iterating it!

    The fix is easy enough, make a copy of wordList and iterate that instead, then it all works:

    #!/usr/bin/python
    
    import collections
    
    class Solution(object):
        def ladderLength(self, beginWord, endWord, wordList):
            """
            :type beginWord: str
            :type endWord: str
            :type wordList: List[str]
            :rtype: int
            """
            if beginWord in wordList:
                wordList.remove(beginWord)
            
            if endWord not in wordList:
                return 0
    
            wordList.append(endWord)
            queue = collections.deque([[beginWord, 1]])
            leng = len(beginWord)
            
            while queue:
                word, length = queue.popleft()
                if word == endWord:
                    return length
                wordListCopy = wordList.copy()
                for n in wordListCopy:
                    if sum(n[i]!=word[i] for i in range(leng))==1:
                        wordList.remove(n)
                        queue.append([n,length+1])
            return 0
            
    print(Solution().ladderLength("hot", "dog", ["hot","dog","cog","pot","dot"]))        
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.