Golfed in Python (3 Lines)


  • 0
    D
    class Solution(object):
        def ladderLength(self, beginWord, endWord, wordList):
            def recurse(wordList, cur, depth):
                return -depth if not cur else endWord in cur or 1 + recurse(wordList - cur, wordList - cur & {W[:i] + l + W[i + 1:] 
                            for l in string.ascii_lowercase 
                            for i in range(len(beginWord)) 
                            for W in cur}, depth + 1)
            return recurse(set(wordList), set([beginWord]), 0)
    

    here's my 2 way bfs

    class Solution(object):
        def ladderLength(self, beginWord, endWord, wordList):
            left, right, wordList = set([beginWord]), set([endWord]), set(wordList)
            if endWord not in wordList: return 0
            I, L = range(len(beginWord)), string.ascii_lowercase
            length = 1
            while left and right:
                if left & right:
                    return length
                left, right = sorted([left, right], key=len)
                wordList -= left
                left = wordList & {W[:i] + l + W[i + 1:] for l in L for i in I for W in left}
                length += 1
            return 0
    

Log in to reply
 

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