0127._word_ladder.md

127. Word Ladder

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/word-ladder/description/

内容描述

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.
Example 1:

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

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Example 2:

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

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

解题方案

思路 1

tag可以算BFS，其实就是求shortest path的变体

Reference from kamyu104

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        distance, stack, visited, lookup = 0, [beginWord], set([beginWord]), set(wordList)
        while stack:
            next_stack = []
            for word in stack:
                if word == endWord:
                    return distance + 1
                for i in range(len(word)):
                    for char in 'abcdefghijklmnopqrstuvwxyz':
                        trans_word = word[:i] + char + word[i+1:]
                        if trans_word not in visited and trans_word in lookup:
                            next_stack.append(trans_word)
                            visited.add(trans_word)
            distance += 1
            stack = next_stack
        return 0