Simple one set solution in Python


  • 0
    S
    class Solution(object):
        def ladderLength(self, begin_word, end_word, dict_list):
            length = 2
            words = set([begin_word])
            dict_list.discard(begin_word)
            dict_list.discard(end_word)
            while words:
                new_words = set()
                for word in words:
                    for i in range(len(begin_word)):
                        for c in 'abcdefghijklmnopqrstuvwxyz':
                            new_word = word[:i] + c + word[i+1:]
                            if new_word == end_word:
                                return length
                            if new_word in dict_list:
                                new_words.add(new_word)
                words = new_words
                length += 1
                dict_list -= words
            return 0

  • 0
    Z
    class Solution(object):
        def ladderLength(self, beginWord, endWord, wordList):
            d = {word: len(wordList) + 1 for word in wordList}
            Q = [beginWord]
            level = 2
            while len(Q) > 0:
                newQ = dict()
                for word in Q:
                    for i in range(len(word)):
                        for c in 'abcdefghijklmnopqrstuvwxyz':
                            new_word = word[:i] + c + word[i+1:]
                            if d.get(new_word) is not None and level < d[new_word]:
                                d[new_word] = level
                                newQ[new_word] = True
                            if new_word == endWord:
                                return level
                Q = newQ.keys()
                level += 1
            return 0
    

    Thanks for sharing your solution!
    I implemented this with dictionary, however it only beats 5%.
    I thought d.get(new_word) is better than new_word in dict_list but it isn't actually...can someone explain this?


Log in to reply
 

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