9-liner in Python, simple 1-pass straight-forward BFS, AC


  • 0
    O

    This is an almost straight-forward BFS, with one optimization to get accepted by OJ: pre-caching all the neighbors of all words.

    class Solution(object):
        def findLadders(self, beginWord, endWord, wordList):
            wordList |= set([endWord])
            neib = {w:[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 wordList] for w in wordList}
            visited, q, ret = {}, collections.deque([[beginWord]]), []
            while q and not (ret and len(q[0]) >= len(ret[0])):
                l = q.popleft()
                visited[l[-1]] = True
                for ww in (w for w in neib[l[-1]] if w not in visited):
                    (ret if ww == endWord else q).append(l + [ww])
            return ret
    

  • 0
    C

    @o_sharp
    Too strange!
    Get AC in leetcode, but get KeyError for 'hit' using the given example if I run it on my PC.
    So why does it work though there is no neighbors for the beginword?


  • 0
    O

    @Coastchb Mind if you show me the entire output?


  • 0
    C

    @o_sharp 0_1470920326818_126.png

    So I modify your solution as :
    wordList |= set([beginWord,endWord]).
    But got TLE in leetcode.


Log in to reply
 

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