A Python solution which is easy to understand

  • 1

    Inspired by Peter Norvig's great article: How to Write a Spelling Corrector.

    Basicly, I intersect all the possible replaces of edit distance 1 of a word with the remaining wordDict to search for the next batch of possible transforms until endWord is reached or there are no more moves.
    Python's set() is absolutely an ideal tool for this job, translation from idea to code is direct, smooth and clear by utilizing it.

    import string
    class Solution:
        # @param beginWord, a string
        # @param endWord, a string
        # @param wordDict, a set<string>
        # @return an integer
        def ladderLength(self, beginWord, endWord, wordDict):
            def edit_distance1_set(word):
                return set(
                    a + c + b[1:]
                    for a, b in [(word[:i], word[i:]) for i in range(len(word) + 1)]
                    for c in string.lowercase if b) - set([word])
            def distance(wa, wb):
                count = 0
                for i in range(len(wa)):
                    if wa[i] != wb[i]:
                        count += 1
                return count
            def next_words(word, lst):
                """return a candidates list of word's next transform"""
                return edit_distance1_set(word).intersection(lst)
            if not isinstance(wordDict, set):
                wordDict = set(wordDict)
            if distance(beginWord, endWord) == 1:
                return 2
            landing_zone = next_words(endWord, wordDict)
            if not landing_zone:
                return 0
            explore = set([beginWord])
            remain = wordDict - explore
            depth = 2
            while not (landing_zone.intersection(explore)):
                # print explore
                if not remain:
                    return 0
                # print 'depth:{}, '.format(depth), explore
                old_explore = explore
                explore = set()
                for w in old_explore:
                    explore.update(next_words(w, remain))
                if not explore:
                    return 0
                depth += 1
            # print explore, landing_zone
            return depth

Log in to reply

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