LeetCode--word ladder（python）

題目：

給定一個開始字元串beginWord 如 ‘hit’，結束字元串endWord如‘cog’，字元串字典wordlist 如 ["hot","dot","dog","lot","log","cog"]。從開始字元串開始，要求每次隻能改變一個字元，求經過wordlist到達endWord的最短路徑

解題思路：

考慮到最短路徑，用djistra算法，從開始字元串出發，找到該字元串改變一個字元後可以到達wordlist中的所有字元串。再從新到達的字元串清單出發，計算一步之後可以到達wordlist中之前未到達的所有字元串。經過多次循環，直到新到達的字元串中包含結束字元串，傳回目前步數即可。

注意：

這是一個非常卡時間的題目。需要将原始的字元串字典wordlist存為python中的字典格式，減少搜尋的複雜度（從n到1）

代碼如下(leetcode中AC)：

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        character = 'abcdefghijklmnopqrstuvwxyz'
        def dijkstra(new_list,unreached_list,endWord,count):
            if unreached_list==[] or new_list==[]:
                return 0
            count = count + 1
            list_return = []
            for i in range(len(new_list)):
                for j in range(len(new_list[i])):
                    for k in character:
                        temp = new_list[i]
                        tmp1 = temp[:j]
                        tmp2 = temp[j+1:]
                        temp = tmp1+k+tmp2
                        if temp==new_list[i][j]:
                            continue
                        else:
                            if temp in unreached_list:
                                list_return.append(temp)
                                if temp==endWord:
                                    return count
                                del unreached_list[temp]
            return dijkstra(list_return,unreached_list,endWord,count)
        begin = []
        begin.append(beginWord)
        dict_unreach = {}
        for i in range(len(wordList)):
            if wordList[i] not in dict_unreach:
                dict_unreach[wordList[i]] = 1
        return dijkstra(begin,dict_unreach,endWord,1)