leetcode-127-Word-Ladder

描述


A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

  • Every adjacent pair of words differs by a single letter.
  • Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
  • sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Example 1:

1
2
3
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

Example 2:

1
2
3
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

Constraints:

  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • wordList[i].length == beginWord.length
  • beginWord, endWord, and wordList[i] consist of lowercase English letters.
  • beginWord != endWord
  • All the words in wordList are unique.

分析


先建图,然后再做广度优先搜索。具体来说,先将每个单词抽象为一个点,如果两个单词可以只改变一个字母进行转换,那么他们之间有一条双向边。我们只需要把满足转换条件的点相连,就形成了一张图。这里有个技巧是 单词 abc 可以与虚拟节点 bc, ac, ab* 建立双向连接,最后进行广度优先搜索,最后返回距离除以2加1即可。

解决方案1(Python)


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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
wordIDMap = dict()
edge = collections.defaultdict(list)
self.nodeNum = 0

def addWord(word):
if word not in wordIDMap:
wordIDMap[word] = self.nodeNum
self.nodeNum += 1

def addEdge(word):
addWord(word)
id1 = wordIDMap[word]
wordChars = list(word)
for i in range(len(wordChars)):
nowChar = wordChars[i]
wordChars[i] = "*"
newWord = "".join(wordChars)
addWord(newWord)
id2 = wordIDMap[newWord]
edge[id1].append(id2)
edge[id2].append(id1)
wordChars[i] = nowChar
for word in wordList:
addEdge(word)

addEdge(beginWord)
if endWord not in wordIDMap:
return 0

distance = [float("inf")] * self.nodeNum
beginID, endID = wordIDMap[beginWord], wordIDMap[endWord]
distance[beginID] = 0

queue = collections.deque([beginID])
while queue:
now = queue.popleft()
if now == endID:
return distance[endID] // 2 + 1
for nextChar in edge[now]:
if distance[nextChar] == float("inf"):
distance[nextChar] = distance[now] + 1
queue.append(nextChar)
return 0

相关问题


题目来源