127. Word Ladder Leetcode Python


Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit"-> "hot"-> "dot"-> "dog"-> "cog",
return its length 5.
Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
この問題はbreadth first searchで各アルファベットを1つのedgeとして1つのqueで毎回得られた新しいedgeを追加しdictの中ですでに遍歴したノードを削除した.
新しい単語ごとの複雑さはL×26 Lは単語の長さです
コードは次のとおりです.
class Solution:
    # @param start, a string
    # @param end, a string
    # @param dict, a set of string
    # @return an integer
    def ladderLength(self, start, end, dict):
        dict.add(end)
        q=[]
        q.append((start,1))
        while q:
            curr=q.pop(0)
            curword=curr[0]
            curlen=curr[1]
            if curword==end:
                return curlen
            for i in range(len(curword)):
                part1=curword[:i]
                part2=curword[i+1:]
                for j in 'qwertyuiopasdfghjklzxcvbnm':
                    if curword[i]!=j:
                        nextword=part1+j+part2
                        if nextword in dict:
                            q.append((nextword,curlen+1))
                            dict.remove(nextword)
        return 0