Skip to content

126 Word Ladder II

126. Word Ladder II

题目:

https://leetcode.com/problems/word-ladder-ii/

难度:

Hard

其实关键在于怎么优化和表示图

思路来自1p3a:

这题目实在是太适合python了  如此简洁

就是基本的bfs,典型的level order traverse 有两个坑:

  1. 不要判断字典里的某两个word是否只相差一个字母,而是要判断某个word的邻居(和他只相差一个字母的所有word)是否在字典里,这样的改进会使这一步的复杂度下降很多,否则超时妥妥
  2. 每一轮访问过的word一定要从字典中删除掉,否则一定会超时

最后见到end word就收 完成

拿题目的例子来看:

```\ hit | hot / \ dot lot | | dog log \ / cog


routine 字典,然后再根据这个来寻找路径

`{'cog': ['log', 'dog'], 'hit': [], 'log': ['lot'], 'dog': ['dot'], 'hot': ['hit'], 'lot': ['hot'], 'dot': ['hot']}`

```'cog': ['log', 'dog']```这里的意思就是说在走到```'cog'```之前尝试过了```'log'```和```'dog'```,即previous tried node

而生成字典的过程就是BFS的,此处保证寻找的路径就是最短的。

AC代码:

```python
class Solution(object):
    def findLadders(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: List[List[str]]
        """

        def backtrack(result, trace, path, word):
            if len(trace[word]) == 0:
                result.append([word] + path)
            else:
                for prev in trace[word]:
                    backtrack(result, trace, [word] + path, prev)

        lookup = set(wordList) | set([beginWord])
        res, cur, routine = [], set([beginWord]), {word: [] for word in lookup}
        while cur and endWord not in cur:
            next_queue = set()
            for word in cur:
                lookup.remove(word)
            for word in cur:
                for i in range(len(word)):
                    for j in 'abcdefghijklmnopqrstuvwxyz':
                        candidate = word[:i] + j + word[i + 1:]
                        if candidate in lookup:
                            next_queue.add(candidate)
                            routine[candidate].append(word)
            cur = next_queue

        if cur:
            backtrack(res, routine, [], endWord)
        return res

这样可以beat 69.09%



回到顶部