题目链接 : https://leetcode-cn.com/problems/word-ladder-ii/
题目描述:
给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：
- 每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:
如果不存在这样的转换序列，返回一个空列表。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例:
示例 1:
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出:
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
示例 2:
输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出: []
解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。
思路:
这道题 BFS + DFS
用BFS求从beginWord 到endWord最短距离,经过哪些单词, 用字典记录离beginWord的距离;
用DFS求从beginWord 到endWord有哪些路径
Java 代码写的我怀疑人生, 可以帮我简化吗?
代码:
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
from collections import defaultdict
wordList = set(wordList)
res = []
# 记录单词下一步能转到的单词
next_word_dict = defaultdict(list)
# 记录到beginWord距离
distance = {}
distance[beginWord] = 0
# 找一个单词能转到的单词
def next_word(word):
ans = []
for i in range(len(word)):
for j in range(97, 123):
tmp = word[:i] + chr(j) + word[i + 1:]
if tmp != word and tmp in wordList:
ans.append(tmp)
return ans
# 求到beginWord的距离
def bfs():
cur = [beginWord]
step = 0
flag = False
while cur:
step += 1
next_time = []
for word in cur:
for nw in next_word(word):
next_word_dict[word].append(nw)
if nw == endWord:
flag = True
if nw not in distance:
distance[nw] = step
next_time.append(nw)
if flag:
break
cur = next_time
# 遍历所有从beginWord到endWord的路径
def dfs(tmp, step):
if tmp[-1] == endWord:
res.append(tmp)
return
for word in next_word_dict[tmp[-1]]:
if distance[word] == step + 1:
dfs(tmp + [word], step + 1)
bfs()
dfs([beginWord], 0)
return res
java
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
Set<String> wordList_set = new HashSet<>(wordList);
List<List<String>> res = new ArrayList<>();
Map<String, ArrayList<String>> next_word_map = new HashMap<>();
Map<String, Integer> distance = new HashMap<>();
bfs(beginWord, endWord, next_word_map, distance, wordList_set);
dfs(beginWord, endWord, next_word_map, 0, res, new ArrayList<String>(Arrays.asList(beginWord)), distance);
return res;
}
private void dfs(String beginWord, String endWord, Map<String, ArrayList<String>> next_word_map, int step, List<List<String>> res, ArrayList<String> tmp, Map<String, Integer> distance) {
if (tmp.get(tmp.size() - 1).equals(endWord)) res.add(new ArrayList<>(tmp));
for (String word : next_word_map.get(tmp.get(tmp.size() - 1))) {
tmp.add(word);
if (distance.get(word) == step + 1) dfs(word, endWord, next_word_map, step + 1, res, tmp, distance);
tmp.remove(tmp.size() - 1);
}
}
private void bfs(String beginWord, String endWord, Map<String, ArrayList<String>> next_word_map, Map<String, Integer> distance, Set<String> wordList_set) {
for (String s : wordList_set) next_word_map.put(s, new ArrayList<String>());
next_word_map.put(beginWord, new ArrayList<>());
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
distance.put(beginWord, 0);
boolean flag = false;
int step = 0;
while (!queue.isEmpty()) {
step++;
int n = queue.size();
for (int i = 0; i < n; i++) {
String word = queue.poll();
for (String nw : next_word(word, wordList_set)
) {
next_word_map.getOrDefault(word, new ArrayList<>()).add(nw);
if (nw.equals(endWord)) flag = true;
if (!distance.containsKey(nw)){
distance.put(nw, step);
queue.offer(nw);
}
}
}
if (flag) break;
}
}
private ArrayList<String> next_word(String word, Set<String> wordList_set) {
ArrayList<String> ans = new ArrayList<>();
for (int i = 0; i < word.length(); i++) {
char[] chars = word.toCharArray();
for (char ch = 'a'; ch <= 'z'; ch++) {
chars[i] = ch;
String tmp = new String(chars);
if (!tmp.equals(word) && wordList_set.contains(tmp)) ans.add(tmp);
}
}
return ans;
}
}
