- Word Ladder
困难
https://leetcode-cn.com/problems/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:
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:
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.
相关企业
- 亚马逊 Amazon|36
- Facebook|13
- 微软 Microsoft|7
- 苹果 Apple|5
- 字节跳动|4
相关标签
- Breadth-First Search
- Hash Table
- String
相似题目
- Word Ladder II 困难
- Minimum Genetic Mutation 中等
不能用DP
因为层次性不够， 不能分层。（一个点一定在另一个点前面）
这是简单图最短路径问题，所以一定是BFS。
1
target = A
for word in words_B: # O(N)
check edit_distance between A, B: # O(L) L is #letters of B
if == 1:
returnO(N * L)
2
target = A
for letter in word_A: # O(L)
for 25: # O(25)
A' = A change this letter
if A' in words_B: # O(L)
returnO(25 * L * L) = O(L^2)
In most cases, N >> L, so second one is better.
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList:
return 0
queue = collections.deque([beginWord])
visited_and_distance = dict({beginWord: 1})
while queue:
curr_word = queue.popleft()
if curr_word == endWord:
return visited_and_distance[curr_word]
for next_word in self.getAllPossibleNextWords(curr_word):
if next_word in visited_and_distance or next_word not in wordList:
continue
queue.append(next_word)
visited_and_distance[next_word] = visited_and_distance[curr_word] + 1
return 0
def getAllPossibleNextWords(self, word):
next_words = []
for i in range(len(word)):
# one next word consists of leffpart, iletter, rightpart
leftpart, rightpart = word[:i], word[i+1:]
for char in "abcdefghijklmnopqrstuvwxyz": # change only one letter
if word[i] == char:
continue
next_words.append(leftpart + char + rightpart)
return next_wordsclass Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
word_set = set(wordList) # only change
if endWord not in word_set:
return 0
queue = collections.deque([beginWord])
visited_and_distance = dict({beginWord: 1})
while queue:
curr_word = queue.popleft()
if curr_word == endWord:
return visited_and_distance[curr_word]
for next_word in self.getAllPossibleNextWords(curr_word):
if next_word in visited_and_distance or next_word not in word_set:
continue
queue.append(next_word)
visited_and_distance[next_word] = visited_and_distance[curr_word] + 1
return 0
def getAllPossibleNextWords(self, word):
next_words = []
for i in range(len(word)):
# one next word consists of leffpart, iletter, rightpart
leftpart, rightpart = word[:i], word[i+1:]
for char in "abcdefghijklmnopqrstuvwxyz": # change only one letter
if word[i] == char:
continue
next_words.append(leftpart + char + rightpart)
return next_wordsclass Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if not wordList:
return 0
wordset = set(wordList)
if endWord not in wordset:
return 0
queue = collections.deque([beginWord])
visited = set([beginWord])
distance = 0
while queue:
distance += 1
currsize = len(queue)
for i in range(currsize):
currword = queue.popleft()
if currword == endWord:
return distance
for nextword in self.getAllPossibleNextWords(currword):
if nextword in visited or nextword not in wordset:
continue
queue.append(nextword)
visited.add(nextword)
return 0
def getAllPossibleNextWords(self, word):
nextwords = []
for i in range(len(word)):
leftpart, rightpart = word[:i], word[i+1:]
for char in "abcdefghijklmnopqrstuvwxyz":
if char == word[i]:
continue
nextwords.append(leftpart + char + rightpart)
return nextwords代码改动其实比较小
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if not wordList:
return 0
wordset = set(wordList)
if endWord not in wordset:
return 0
forward_queue = collections.deque([beginWord])
forward_visited = set([beginWord])
backward_queue = collections.deque([endWord])
backward_visited = set([endWord])
distance = 0
while forward_queue and backward_queue:
distance += 1
currsize = len(forward_queue)
for i in range(currsize):
currword = forward_queue.popleft()
for nextword in self.getAllPossibleNextWords(currword):
if nextword in backward_visited:
return distance+1
if nextword in forward_visited or nextword not in wordset:
continue
forward_queue.append(nextword)
forward_visited.add(nextword)
distance += 1
currsize = len(backward_queue)
for i in range(currsize):
currword = backward_queue.popleft()
for nextword in self.getAllPossibleNextWords(currword):
if nextword in forward_visited:
return distance+1
if nextword in backward_visited or nextword not in wordset:
continue
backward_queue.append(nextword)
backward_visited.add(nextword)
return 0
def getAllPossibleNextWords(self, word):
nextwords = []
for i in range(len(word)):
leftpart, rightpart = word[:i], word[i+1:]
for char in "abcdefghijklmnopqrstuvwxyz":
if char == word[i]:
continue
nextwords.append(leftpart + char + rightpart)
return nextwords