7-liner in Python

  • 1

    This is a plain BFS solution.

    class Solution(object):
        def ladderLength(self, beginWord, endWord, wordList):
            d, q = {w:True for w in wordList}, collections.deque([(beginWord, 2)])
            while q and sum(1 for c1, c2 in zip(q[0][0], endWord) if c1!=c2) != 1:
                w, k = q.popleft()
                for ww in (w[:i]+c2+w[i+1:] for i, c in enumerate(w) for c2 in 'abcdefghijklmnopqrstuvwxyz' if c2!=c and w[:i]+c2+w[i+1:] in d):
                    q.append((ww, k+1))
                    del d[ww]
            return q[0][1] if q else 0

Log in to reply

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