leetcode——单词接龙_leetcode 单词接龙

 126. 单词接龙 

给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则： 每次转换只能改变一个字母。 转换后得到的单词必须是字典中的单词。 说明: 如果不存在这样的转换序列，返回一个空列表。 所有单词具有相同的长度。 所有单词只由小写字母组成。 字典中不存在重复的单词。 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

示例 1:
 
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
 
输出:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]
示例 2:
 
输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
 
输出: []

 解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。

代码

1 先上一个最终的版本，其实是仿照大佬代码照猫画虎的

class Solution2:
    def findLadders(self, beginWord, endWord, wordList):
        if endWord not in wordList:
            return 0
        s1 = {beginWord}
        s2 = {endWord}
        step = 0
        while s1 and s2:
            if len(s1)>len(s2):s1, s2 = s2, s1
            step += 1
            s = set()
            for preword in s1:
                n = len(preword)
                next_words = [preword[:i] + chr(j) + preword[i+1:] for j in range(97, 123) for i in range(n)]
                for word in next_words:
                    if word in s2:
                        return step + 1
                    if word not in wordList:
                        continue
                    wordList.remove(word)
                    s.add(word)
            s1 = s
        return 0

 

接着说一下我的心路历程

开始看到这道题没啥思路，感觉求起来太麻烦。。。 可能对路径这种题有点不知所措。。。 后来简单看了下解题思路 ，有一种替换映射词表的逻辑， 就是例如key = “a*b”， value = 满足’a*b‘ 的词典中的单词， *表示任意字符，也就是获取有一位字母不一样的单词有哪些

class Solution:
    def get_word_dic(self, wordList):
        dic = dict()
        for word in wordList:
            for i in range(len(word)):
                mark = word[:i] + '*' + word[i + 1:]
                dic.setdefault(mark, [])
                if word not in dic[mark]:
                    dic[mark].append(word)
        return dic
 
    def find(self, pre_word_lists, endWord, dic):
        if len(pre_word_lists)==0:
            return []
        res = []
        level1_word_lists = []
        for pre_word_list in pre_word_lists:
            beginWord = pre_word_list[-1]
            level1_words = set()
            for i in range(len(beginWord)):
                mark = beginWord[:i] + '*' + beginWord[i + 1:]
                if mark not in dic:
                    continue
                if endWord in dic[mark]:
                    res.append(pre_word_list + [endWord])
                level1_words.update([x for x in dic[mark] if x not in pre_word_list])
            level1_word_lists.extend([pre_word_list + [x] for x in level1_words])
        if len(res) > 0:
            return res
        paths = self.find(level1_word_lists, endWord, dic)
        if len(paths) > 0:
            return paths
        return []
 
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0
        dic = self.get_word_dic(wordList)
        paths = self.find([[beginWord]], endWord, dic)
        if len(paths)==0:
            return 0
        return len(paths[0])

超时了，然后看了看大牛的思路，写了最上面的那个代码，但是还是有点不甘心啊，想找找我的代码哪里慢。

双向这个问题就不用多说了，肯定是影响很大的，但是测了下时间， 把双向那句 if len(s1)>len(s2):s1, s2 = s2, s1 注掉，依然是比我的快很多的。

探索是不是每次从词典里面查比较费时，改成 像最上面代码中的a-z替换的逻辑.， 提交后依然超时了。

再看看其它的地方，感觉是词典remove的问题，加上词典remove的操作 ，如下代码， 提交还是会超时，但是过了更多的测试用例

class Solution:
 
    def find(self, pre_word_lists, endWord, wordList):
        if len(pre_word_lists)==0:
            return 0
        level1_word_lists = []
        for pre_word_list in pre_word_lists:
            beginWord = pre_word_list[-1]
 
            nextword = []
            for i in range(len(beginWord)):
                for j in range(97, 123):
                    word = beginWord[:i] + chr(j) + beginWord[i + 1:]
                    if word in wordList and word not in pre_word_list:
                        nextword.append(word)
                        wordList.remove(word)
            if endWord in nextword:
                return len(pre_word_list + [endWord])
            level1_word_lists.extend([pre_word_list + [x] for x in nextword])
        return self.find(level1_word_lists, endWord, wordList)
 
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0
        return self.find([[beginWord]], endWord, wordList)

 

发现最后还是得改成双向的才行，不然词典太长，路径太多，还是会引起爆炸的路径搜索问题...