## 题目描述：

Given two words (beginWord and endWord), and a dictionary, 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 dictionary

For example,

Given:

```start = "hit"
end = "cog"
dict = ["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.

## 题目大意：

```start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]```

## 解题思路：

``````for word in wordDict:
for x in range(len(word)):
token = word[:x] + '_' + word[x+1:]
neighbors[token] += word,
``````

## Python代码：

``````class Solution:
# @param {string} beginWord
# @param {string} endWord
# @param {set<string>} wordDict
# @return {integer}
from collections import defaultdict, deque
queue = deque( [ [beginWord, 1] ] )
visited = set( [ beginWord ] )
neighbors = defaultdict(list)
for word in wordDict:
for x in range(len(word)):
token = word[:x] + '_' + word[x+1:]
neighbors[token] += word,
while queue:
word, length = queue.popleft()
if self.wordDist(word, endWord) <= 1:
return length + 1
for x in range(len(word)):
token = word[:x] + '_' + word[x+1:]
queue += [ladder, length + 1],
return 0
def wordDist(self, wordA, wordB):
return sum([wordA[x] != wordB[x] for x in range(len(wordA))])
``````

## Python代码：

``````class Solution:
# @param {string} beginWord
# @param {string} endWord
# @param {set<string>} wordDict
# @return {integer}
from collections import defaultdict, deque
qf = deque( [ [beginWord, 0] ] )
qe = deque( [ [endWord, 0] ] )
sf = { }
se = { }
neighbors = defaultdict(list)
for word in wordDict:
for x in range(len(word)):
token = word[:x] + '_' + word[x+1:]
neighbors[token] += word,
while qf or qe:
if qf:
word, length = qf.popleft()
if word in se :
return length + se[word] + 1
for x in range(len(word)):
token = word[:x] + '_' + word[x+1:]
qf += [ladder, length + 1],
if qe:
word, length = qe.popleft()
if word in sf :
return length + sf[word] + 1
for x in range(len(word)):
token = word[:x] + '_' + word[x+1:]
qe += [ladder, length + 1],
return 0
``````

Pingbacks已关闭。