{"id":3430,"date":"2020-04-03T13:19:57","date_gmt":"2020-04-03T05:19:57","guid":{"rendered":"http:\/\/www.sniper97.cn\/?p=3430"},"modified":"2020-04-03T13:19:57","modified_gmt":"2020-04-03T05:19:57","slug":"%e3%80%90leetcode%e3%80%910127-%e5%8d%95%e8%af%8d%e6%8e%a5%e9%be%99","status":"publish","type":"post","link":"http:\/\/www.sniper97.cn\/index.php\/note\/algorithm\/3430\/","title":{"rendered":"\u3010LeetCode\u3011*0127 \u5355\u8bcd\u63a5\u9f99"},"content":{"rendered":"\n

https:\/\/leetcode-cn.com\/problems\/word-ladder\/<\/a><\/p>\n\n\n

# -*- coding:utf-8 -*-

\"\"\"
<\/em>      \u250f\u251b \u253b\u2501\u2501\u2501\u2501\u2501\u251b \u253b\u2513
<\/em>      \u2503<\/em>\u3000\u3000\u3000\u3000\u3000\u3000<\/em> \u2503
<\/em>      \u2503<\/em>\u3000\u3000\u3000<\/em>\u2501<\/em>\u3000\u3000\u3000<\/em>\u2503
<\/em>      \u2503<\/em>\u3000<\/em>\u2533\u251b<\/em>\u3000<\/em>  \u2517\u2533<\/em>\u3000<\/em>\u2503
<\/em>      \u2503<\/em>\u3000\u3000\u3000\u3000\u3000\u3000<\/em> \u2503
<\/em>      \u2503<\/em>\u3000\u3000\u3000<\/em>\u253b<\/em>\u3000\u3000\u3000<\/em>\u2503
<\/em>      \u2503<\/em>\u3000\u3000\u3000\u3000\u3000\u3000<\/em> \u2503
<\/em>      \u2517\u2501\u2513<\/em>\u3000\u3000\u3000<\/em>\u250f\u2501\u2501\u2501\u251b
<\/em>        \u2503<\/em>\u3000\u3000\u3000<\/em>\u2503   <\/em>\u795e\u517d\u4fdd\u4f51<\/em>
<\/em>        \u2503<\/em>\u3000\u3000\u3000<\/em>\u2503   <\/em>\u4ee3\u7801\u65e0<\/em>BUG<\/em>\uff01<\/em>
<\/em>        \u2503<\/em>\u3000\u3000\u3000<\/em>\u2517\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2513
<\/em>        \u2503<\/em>\u3000\u3000\u3000\u3000\u3000\u3000\u3000<\/em>    \u2523\u2513
<\/em>        \u2503<\/em>\u3000\u3000\u3000\u3000<\/em>         \u250f\u251b
<\/em>        \u2517\u2501\u2513 \u2513 \u250f\u2501\u2501\u2501\u2533 \u2513 \u250f\u2501\u251b
<\/em>          \u2503 \u252b \u252b   \u2503 \u252b \u252b
<\/em>          \u2517\u2501\u253b\u2501\u251b   \u2517\u2501\u253b\u2501\u251b
<\/em>\"\"\"
<\/em>from collections import defaultdict

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        \"\"\"
<\/em>        <\/em>:type<\/em><\/strong> beginWord: str
<\/em>        <\/em>:type<\/em><\/strong> endWord: str
<\/em>        <\/em>:type<\/em><\/strong> wordList: List[str]
<\/em>        <\/em>:rtype<\/em><\/strong>: int
<\/em>        \"\"\"
<\/em>        <\/em>if endWord not in wordList or not endWord or not beginWord or not wordList:
            return 0

        L = len(beginWord)

        all_combo_dict = defaultdict(list)
        for word in wordList:
            for i in range(L):
                all_combo_dict[word[:i] + \"*\" + word[i + 1:]].append(word)

        queue = [(beginWord, 1)]
        visited = {beginWord: True}
        while queue:
            current_word, level = queue.pop(0)
            for i in range(L):
                intermediate_word = current_word[:i] + \"*\" + current_word[i + 1:]

                for word in all_combo_dict[intermediate_word]:
                    if word == endWord:
                        return level + 1
                    if word not in visited:
                        visited[word] = True
                        queue.append((word, level + 1))
                all_combo_dict[intermediate_word] = []
        return 0



if __name__ == '__main__':
    beginWord = \"hit\"
    endWord = \"cog\"
    wordList = [\"hot\", \"dot\", \"dog\", \"lot\", \"log\", \"cog\"]
    print(Solution().ladderLength(beginWord, endWord, wordList))
<\/pre>\n\n\n
\u601d\u8def\uff1a<\/strong>\u611f\u89c9\u81ea\u5df1\u9000\u6b65\u4e86\u3002\u3002<\/p>\n\n\n
\u8fd9\u9053\u9898BFS\uff0c\u7528\u5b57\u5178\u8bb0\u5f55\u5df2\u7ecf\u5339\u914d\u8fc7\u7684\u5355\u8bcd\u9632\u6b62\u51fa\u73b0\u73af\u3002<\/p>\n\n\n
\u4e0a\u9762\u7684\u5f88\u591a\u5b57\u5178\u53ef\u4ee5\u66ff\u6362\u6210\u5217\u8868\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
https:\/\/leetcode-cn.com\/problems\/word-ladder\/ # -* […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_mi_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[10],"tags":[],"views":7080,"_links":{"self":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/3430"}],"collection":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/comments?post=3430"}],"version-history":[{"count":0,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/3430\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/media?parent=3430"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/categories?post=3430"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/tags?post=3430"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}