Jianbo Dai's

lc127.单词接龙

 
  • Jan 24, 2021

题目链接

这个题没什么思路，还以为和编辑距离有关系，要先求出每对词的编辑距离然后判断之类的，不过估计这种思路是不可行的或者有比较大的时间复杂度（好像确实）？就看了一下题解，用的是bfs和双向bfs。首先呢我们先考虑去建图。我们注意到有说明是“每个单词的长度相同”并且“字母都是小写”，所以不同于上面讲到的将每两个单词都判断是否他们之间有路径，我们用的方法是，依次从a到z变换一个选定单词中的每个字母然后去判断新生成的单词是否在词典之中，如果是的话就说明这两个单词之间有边，按照这样的思想可以建立起一个无向图。接下来，由于我们要找一条最短的路径，我们要使用bfs来做，当然我们知道dfs也能做只是bfs可以在找到答案的时候马上停止遍历而非像dfs一样有可能遍历所有点。注意，我们在遍历图的时候，一定要标记掉以及触及的节点否则有可能会尝试循环从而死循环，在这里我们用一个visited的集合来实现。

这个算法的时间复杂度是O（26xWordLength），空间复杂度是O（26xWordLength）。

另外，既然我们知道了起始单词和结尾单词，我们其实可以用双向bfs来解决问题，会稍微优化一点时间复杂度。

python:

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        word_set = set(wordList)
        if len(word_set) == 0 or endWord not in word_set:
            return 0
        
        if beginWord in word_set:
            word_set.remove(beginWord)

        queue = collections.deque()
        queue.append(beginWord)

        visited = set()
        visited.add(beginWord)

        word_len = len(beginWord)
        step = 1
        while queue:
            current_size = len(queue)
            for i in range(current_size):
                word = queue.popleft()
            
                word_list = list(word)
                for j in range(word_len):
                    origin_char = word_list[j]

                    for k in range(26):
                        word_list[j] = chr(ord("a")+k)
                        next_word = "".join(word_list)
                        if next_word in word_set:
                            if next_word == endWord:
                                return step + 1
                            if next_word not in visited:
                                queue.append(next_word)
                                visited.add(next_word)
                    word_list[j] = origin_char
            step += 1
        return 0
Search