class Solution {
public:
vector<string> findLadders(string beginWord, string endWord, vector<string>& wordList) {
}
};
面试题 17.22. 单词转换
给定字典中的两个词，长度相等。写一个方法，把一个词转换成另一个词， 但是一次只能改变一个字符。每一步得到的新词都必须能在字典中找到。
编写一个程序，返回一个可能的转换序列。如有多个可能的转换序列，你可以返回任何一个。
示例 1:
输入: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] 输出: ["hit","hot","dot","lot","log","cog"]
示例 2:
输入: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"] 输出: [] 解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。
原站题解
golang 解法, 执行用时: 16 ms, 内存消耗: 6.5 MB, 提交时间: 2022-12-02 11:20:41
func findLadders(beginWord string, endWord string, wordList []string) []string {
path := map[string][]string{beginWord: []string{beginWord}, endWord: []string{endWord}}
startQueue := map[string]bool{beginWord: true}
endQueue := map[string]bool{endWord: true}
wordDict := make(map[string]bool)
for _, word := range wordList {
wordDict[word] = true
}
if !wordDict[endWord] {
return nil
}
// 用来记录是否为正向遍历，因为反向遍历时记录新路径的方向与正向遍历相反
isBackward := false
for len(startQueue) > 0 && len(endQueue) > 0 {
if len(startQueue) > len(endQueue) {
startQueue, endQueue = endQueue, startQueue
isBackward = !isBackward
}
tempQueue := make(map[string]bool)
for word := range startQueue {
chars := []byte(word)
for i := 0; i < len(chars); i++ {
old := chars[i]
for j := byte('a'); j <= 'z'; j++ {
chars[i] = j
newWord := string(chars)
if endQueue[newWord] {
startLen, endLen := len(path[word]), len(path[newWord])
res := make([]string, startLen + endLen)
if isBackward {
copy(res, path[newWord])
copy(res[endLen:], path[word])
} else {
copy(res, path[word])
copy(res[startLen:], path[newWord])
}
return res
}
if j != old && wordDict[newWord] && len(path[newWord]) == 0 {
path[newWord] = make([]string, len(path[word])+1)
if isBackward {
path[newWord][0] = newWord
copy(path[newWord][1:], path[word])
} else {
copy(path[newWord], path[word])
path[newWord][len(path[newWord])-1] = newWord
}
tempQueue[newWord] = true
}
}
chars[i] = old
}
}
startQueue = tempQueue
}
return nil
}
python3 解法, 执行用时: 128 ms, 内存消耗: 19.4 MB, 提交时间: 2022-12-02 11:18:38
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[str]:
# BFS
hashmap = collections.defaultdict(list)
for word in wordList:
for i in range(len(word)):
hashmap[word[:i] + '*' + word[i + 1:]].append(word)
queue = collections.deque([beginWord])
w_dict = {beginWord: [beginWord]}
while queue:
word = queue.popleft()
if word == endWord:
return w_dict[word]
for i in range(len(word)):
if word[:i] + '*' + word[i + 1:] in hashmap:
for tmp in hashmap[word[:i] + '*' + word[i + 1:]]:
if tmp not in w_dict:
w_dict[tmp] = w_dict[word] + [tmp]
queue.append(tmp)
return []
python3 解法, 执行用时: 108 ms, 内存消耗: 32.9 MB, 提交时间: 2022-12-02 11:18:22
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[str]:
# DFS
hashmap = collections.defaultdict(list)
for word in wordList:
for i in range(len(word)):
hashmap[word[:i] + '*' + word[i + 1:]].append(word)
stack = [beginWord]
w_dict = {beginWord: [beginWord]}
while stack:
word = stack.pop()
if word == endWord:
return w_dict[word]
for i in range(len(word)):
if word[:i] + '*' + word[i + 1:] in hashmap:
for tmp in hashmap[word[:i] + '*' + word[i + 1:]]:
if tmp not in w_dict:
w_dict[tmp] = w_dict[word] + [tmp]
stack.append(tmp)
return []