[leetcode-127]word-ladder(单词接龙)

加强下算法题的训练，加油鸭～～～

题目

给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

• 每次转换只能改变一个字母。
• 转换过程中的中间单词必须是字典中的单词。

说明:

• 如果不存在这样的转换序列，返回 0。
• 所有单词具有相同的长度。
• 所有单词只由小写字母组成。
• 字典中不存在重复的单词。
• 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

示例1:

输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

输出: 5

解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
     返回它的长度 5。

示例2:

输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

输出: 0

解释: endWord "cog" 不在字典中，所以无法进行转换。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-ladder

解答

from typing import List

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        import queue
        if endWord not in wordList:
            return 0
        if beginWord not in wordList:
            wordList.append(beginWord)
        # 定义 word_seeds 为一个单词将任意一个字符替换为 * 后的字符串列表　如　hit 的 word_seeds 为 *it h*t hi*
        def get_word_seeds(word):
            word_seeds = []
            for index, _ in enumerate(word):
                if index == 0:
                    word_seeds.append('*' + word[1:])
                elif index == len(word)-1:
                    word_seeds.append(word[:-1] + '*')
                else:
                    word_seeds.append(word[:index] + '*' + word[index+1:])
            return word_seeds
        # 定义一个函数，用于获取所有的邻近单词
        def get_next_level_words(word, word_net):
            word_seeds = get_word_seeds(word)
            next_level_words = set()
            for word_seed in word_seeds:
                _next_level_words = word_net[word_seed]
                for _word in _next_level_words:
                    if _word != word:
                        next_level_words.add(_word)
            return list(next_level_words)
        # 定义一个字典，key 为 word seed, value 为包含　word_seed 的单词列表
        word_net = {}
        for word in wordList:
            word_seeds = get_word_seeds(word)
            for word_seed in word_seeds:
                if word_seed not in word_net:
                    word_net[word_seed] = [word]
                else:
                    word_net[word_seed].append(word)
        q = queue.Queue()
        q.put((beginWord, 1))
        # 定义一个字典，用于存储已近搜查过的单词，避免循环搜查
        researched_words = set()
        while not q.empty():
            word, level = q.get()
            if word == endWord:
                return level
            researched_words.add(word)
            next_level_words = get_next_level_words(word, word_net)
            for _word in next_level_words:
                if _word not in researched_words:
                    q.put((_word, level+1))
        return 0
            

def main():
    beginWord = "hit"
    endWord = "cog"
    wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
    result = Solution().ladderLength(beginWord, endWord, wordList)
    print(result)

if __name__ == "__main__":
    main()

修改了下，用字典去存图，本地运行没问题，但是提交到 leetcode 居然没过。郁闷

import queue
class Solution():
    def word_ladder(self, beginWord, endWord, wordList):       
        # 如果目标单词不在列表中，则返回 0        
        if endWord not in wordList:
            return 0        
        # 如果 beginWrod 不在列表中，则加入列表，方便构建图        
        if beginWord not in wordList:            
            wordList.append(beginWord)
        # 定义一个函数，将 word 的每个字母逐一替换为 * 作为 word_seed        
        def get_word_seeds(word):            
            word_seeds = []            
            for index in range(len(word)):                
                if index == 0:                    
                    word_seeds.append("*" + word[1:])                
                elif index == len(word) - 1:                    
                    word_seeds.append(word[:-1] + "*")                
                else:                    
                    word_seeds.append(word[:index] + "*" + word[index+1:])            
            return word_seeds
        # 构建图，结构为 dic, key 为单词，value 为该单词可以一步转换的其他单词列表（不包含自身）        
        word_net = {}        
        for word in wordList:            
            next_level_words = []            
            word_seeds = get_word_seeds(word)            
            for _word in wordList:                
                if _word != word:                    
                    _word_seeds = get_word_seeds(_word)                    
                    # 如果两个单词的 word_seeds 有交集，即合并为集合后的长度小于二者长度和，则两单词相邻，可一步转换到位                    
                    if len(set(word_seeds + _word_seeds)) < len(word_seeds) + len(_word_seeds):                        
                        next_level_words.append(_word)            
            word_net[word] = next_level_words
        # 利用队列进行广度优先搜索, beginWord 入列，且用 researced_words 集合记录已经搜索过的单词        
        q = queue.Queue()        
        researced_words = set()        
        q.put((beginWord, 1))        
        researced_words.add(beginWord)        
        final_level = 0        
        while not q.empty():            
            word, level = q.get()            
            # 如果匹配到目标，则返回该单词的 level，否则将该单词的下一层单词（未搜索过）入列            
            if word == endWord:                
                final_level = level                
                break            
            researced_words.add(word)            
            next_level_words = word_net[word]            
            for _word in next_level_words:                
                if _word not in researced_words:                    
                    q.put((_word, level + 1))
        return final_level

def main():    
    beginWord = "hit"    
    endWord = "cog"    
    word_List = ["hot", "dot", "dog", "cog"]    
    result = Solution().word_ladder(beginWord, endWord, word_List)    
    print(result)
if __name__ == "__main__":    
    main()

结果

提交时间　提交结果　执行用时　内存消耗　语言
几秒前 　通过 　　2972 ms 19.3 MB Python3

讨论

效率不是很高，需要改进