Share my two Python solutions: a very concise one (12 lines, ~160ms) and an optimized solution(~100ms)


  • 47
    D

    The idea behind the first solution is to use character flopping plus bidirectional BFS. Use set operations as much as possible.

    class Solution:
        # @param {string} beginWord
        # @param {string} endWord
        # @param {set<string>} wordDict
        # @return {integer}
        def ladderLength(self, beginWord, endWord, wordDict):
            length = 2
            front, back = set([beginWord]), set([endWord])
            wordDict.discard(beginWord)
            while front:
                # generate all valid transformations
                front = wordDict & (set(word[:index] + ch + word[index+1:] for word in front 
                                    for index in range(len(beginWord)) for ch in 'abcdefghijklmnopqrstuvwxyz'))
                if front & back:
                    # there are common elements in front and back, done
                    return length
                length += 1
                if len(front) > len(back):
                    # swap front and back for better performance (fewer choices in generating nextSet)
                    front, back = back, front
                # remove transformations from wordDict to avoid cycle
                wordDict -= front
            return 0
    

    The optimizations:

    -- Generating next set

    An alternative is to immediately add a candidate to next set if it is in the dictionary.

    Another way to generate next set: for each word in the current set, check if a word in the dictionary can be transformed to it. If it can, add it to the next set. The time complexity of the two methods is analyzed below, assuming word length is L, size of current set and dictionary are M and N, respectively.

    a. character flopping:

    Loop over current set, character of word, alphabet, the flopping itself is O(L). Time complexity is O(26ML^2)

    b. verify transformation:

    Loop over current set, dictionary, character of word. Time complexity is O(MNL)

    For b) to be faster, the switching point is N = 26L. This scale can be adjusted.

    Since the size of dictionary shrinks during the process, it is beneficial to switch to b) in the late stage, or use it for a small dictionary.

    -- Removing current word set from dictionary

    It seems natural to use difference_update for this job since size of dictionary is bigger than that of current word set. But is it so? Note that here we are sure that every word in current set does exist in the dictionary.

    a. S.difference_update(T) or S -= T

    For every key (entry) in T, if it is in S, remove it from T. There are len(T) removes and len(T) peeks.

    b. S.difference(T) or S - T

    Create a new empty set. For every key (entry) in S, if it is not in T, add it to new set. There are len(S)-len(T) adds and len(S) peeks.

    If the sizes of current word set and dictionary are close, using difference_update means we will remove almost everything from dictionary. If we use difference, only a handful of adds. I use size of dictionary is twice that of current word set as the switching point. This threshold can be adjusted too.
    The following optimized code takes ~100ms.

    class Solution:
        # @param {string} beginWord
        # @param {string} endWord
        # @param {set<string>} wordDict
        # @return {integer}
        def ladderLength(self, beginWord, endWord, wordDict):
            def generateNextSet1(current, wordDict, wordLen):
                nextSet = set()
                for word in current:
                    for index in range(wordLen):
                        for ch in 'abcdefghijklmnopqrstuvwxyz':
                            nextWord = word[:index] + ch + word[index+1:]
                            if nextWord in wordDict:
                                nextSet.add(nextWord)
                return nextSet
    
            def generateNextSet2(current, wordDict):
                nextSet = set()
                for word in current:
                    for nextWord in wordDict:
                        index = 0
                        try:
                            while word[index] == nextWord[index]:
                                index += 1
                            if word[index+1:] == nextWord[index+1:]:
                                nextSet.add(nextWord)
                        except:
                            continue
                return nextSet
    
            steps, wordLen = 2, len(beginWord)
            front, back = set([beginWord]), set([endWord])
            wordDict.discard(beginWord)
            switchThreshold = 26*wordLen
            while front:
                # get all valid transformations
                if len(wordDict) >= switchThreshold:
                    front = generateNextSet1(front, wordDict, wordLen)
                else:
                    front = generateNextSet2(front, wordDict)
                if front & back:
                    # there are common elements in front and back, done
                    return steps
                steps += 1
                if len(front) >= len(back):
                    # swap front and back for better performance (smaller nextSet)
                    front, back = back, front
                # remove transformations from wordDict to avoid cycles
                if (len(wordDict)>>1) >= len(front):
                    # s.difference_update(t): O(len(t))
                    wordDict -= front
                else:
                    # s.difference(t): O(len(s))
                    wordDict = wordDict - front
            return 0

  • 6
    E

    Fantastic solution, thanks to you I learned the bidirectional BFS.
    But you solution can't handle input like a,c [b]
    Because the updated "front" set won't have a overlap with "back" set, this can happen if the "set" didn't move inside the dictionary.
    I found this issue when I was thinking why there is no "wordDict.discard(endWord)"
    Here is my improvement upon your solution:

    class Solution:
        # @param {string} beginWord
        # @param {string} endWord
        # @param {set<string>} wordDict
        # @return {integer}
        def ladderLength(self, beginWord, endWord, wordDict):
            front, back=set([beginWord]), set([endWord]) 
            length=2
            width=len(beginWord)
            charSet=list(string.lowercase)
            wordDict.discard(beginWord)
            wordDict.discard(endWord)
            while front:
                newFront=set()
                for phrase in front:
                    for i in xrange(width):
                        for c in charSet:
                            nw=phrase[:i]+c+phrase[i+1:]
                            if nw in back:
                                return length
                            if nw in wordDict:
                                newFront.add(nw)
                front=newFront
                if len(front)>len(back):
                    front,back=back,front
                wordDict-=front
                length+=1
            return 0

  • 1
    D

    Yeah, my solution will fail the a, c, [b] case. But I have found that Leetcode puts both startWord and endWord into dictionary :). Otherwise I can add endWord into the dictionary at the beginning.


  • 0
    Z

    change: charSet=list(string.lowercase)
    to: charSet='abcdefghijklmnopqrstuvwxyz'

    change: for i in xrange(width):
    to: for i in range(width):

    so that it can run on python 3


  • 0
    Z

    if len(front)>len(back):
    front,back=back,front

    this is brilliant!


  • 0
    E

    Thanks for the advice.


  • 1
    D

    Python3 will optimize range to behave the same as xrange in python2.X, and delete key word xrange, So range will be more friendly to python3, not xrange.


  • 0
    C

    i think it can be:

    if nw in wordDict:
      newFront.add(nw)
      wordDict.discard(nw)
    

    to save some time?


  • 0
    E

    @coolgod Yes! so we won't step into this word later. Thanks!


  • 3

    here is my easy-to-understand code:

    import string
    class Solution(object):
        def ladderLength(self, beginWord, endWord, wordList):
            front = {beginWord}
            back = {endWord}
            dist = 1
            wordList = set(wordList)
            word_len = len(beginWord)
            while front:
                dist += 1
                next_front = set()
                for word in front:
                    for i in range(word_len):
                        for c in string.lowercase:
                            if c != word[i]:
                                new_word = word[:i]+c+word[i+1:]
                                if new_word in back:
                                    return dist
                                if new_word in wordList:
                                    next_front.add(new_word)
                                    wordList.remove(new_word)
                front = next_front
                if len(back)<len(front):
                    front, back = back, front
            return 0
    

  • 0

    For endWord corner case.

    class Solution(object):
        def ladderLength(self, beginWord, endWord, wordDict):
            if endWord not in wordDict:
                return 0
            length = 2
            front, back = set([beginWord]), set([endWord])
            wordDict = set(wordDict)
            wordDict.discard(beginWord)
            while front:
                # generate all valid transformations
                front = wordDict & (set(word[:index] + ch + word[index+1:] for word in front 
                                    for index in range(len(beginWord)) for ch in string.ascii_lowercase))
                if front & back:
                    # there are common elements in front and back, done
                    return length
                length += 1
                if len(front) > len(back):
                    # swap front and back for better performance (fewer choices in generating nextSet)
                    front, back = back, front
                # remove transformations from wordDict to avoid cycle
                wordDict -= front
            return 0
    

Log in to reply
 

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