卖萌的弱渣

I am stupid, I am hungry.

Word Ladder

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 intermediate word must exist in the word list

Example:

beginWord = “hit”

endWord = “cog”

wordList = [“hot”,“dot”,“dog”,“lot”,“log”]

As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”,

return its length 5.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

Solution

  • BFS 用stack[word,val] 存当前word 修改一次能到达的所有word
(Word-Ladder.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: Set[str]
        :rtype: int
        """
        alpha = "abcdefghijklmnopqrstuvwxyz"
        n = len(beginWord)
        stack = []
        stack.append([beginWord,1])
        wordList.add(endWord)
        while stack:
            tmp = stack.pop(0)
            word = tmp[0]
            val = tmp[1]
            alpha = "abcdefghijklmnopqrstuvwxyz"
            if word == endWord:
                return val

            for i in range(len(word)):
                for j in alpha:
                    if j == word[i]:
                        continue
                    newWord = word[:i]+j+word[i+1:]
                    if newWord in wordList:
                        stack.append([newWord,val+1])
                        wordList.remove(newWord)
        return 0