每日一道算法题

题目：单词接龙 II

给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：

1. 每次转换只能改变一个字母。
2. 转换过程中的中间单词必须是字典中的单词。

示例 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" 不在字典中，所以不存在符合要求的转换序列。

提示

• 1 <= beginWord.length <= 5
• endWord.length == beginWord.length
• 1 <= wordList.length <= 500
• wordList[i].length == beginWord.length
• beginWord、endWord 和 wordList[i] 由小写英文字母组成
• beginWord!= endWord
• wordList 中的所有单词互不相同

解题思路提示

1. 双向广度优先搜索（BFS）：
   • 常规的广度优先搜索从起始单词开始，一层一层地扩展到目标单词。双向 BFS 则从起始单词和目标单词同时开始扩展，这样可以减少搜索空间，提高效率。
   • 可以使用两个队列，分别存储从起始单词和目标单词开始扩展的单词。
   • 同时，使用两个集合来记录已经访问过的单词，避免重复访问。
2. 构建路径：
   • 在进行双向 BFS 的过程中，不仅要记录每个单词是从哪个单词扩展而来的，还要记录扩展的方向（从起始单词还是目标单词扩展而来）。
   • 当两个方向的搜索相遇时，根据记录的路径信息，从相遇的单词开始，分别向起始单词和目标单词回溯，构建出所有的最短转换序列。
3. 单词转换：
   • 为了快速找到可以通过改变一个字母得到的单词，可以预先构建一个辅助数据结构，例如将每个单词的每个位置的字母替换为通配符（如 *），然后将具有相同通配符形式的单词存储在一个哈希表中。这样在扩展单词时，可以通过通配符快速找到所有可能的转换单词。

 代码实现（JAVA）

import java.util.*;public class WordLadderII {public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {// 存储最终结果List<List<String>> result = new ArrayList<>();// 将 wordList 转换为 HashSet 以提高查找效率Set<String> wordSet = new HashSet<>(wordList);// 如果 endWord 不在 wordSet 中，直接返回空列表if (!wordSet.contains(endWord)) {return result;}// 用于存储每个单词到其前一个单词的映射，用于构建路径Map<String, List<String>> graph = new HashMap<>();// 用于存储从 beginWord 到每个单词的最短距离Map<String, Integer> distance = new HashMap<>();// 初始化队列，将 beginWord 加入队列Queue<String> queue = new LinkedList<>();queue.offer(beginWord);distance.put(beginWord, 0);// 进行广度优先搜索while (!queue.isEmpty()) {int size = queue.size();boolean foundEnd = false;for (int i = 0; i < size; i++) {String currentWord = queue.poll();int currentDistance = distance.get(currentWord);// 生成所有可能的相邻单词List<String> neighbors = getNeighbors(currentWord, wordSet);for (String neighbor : neighbors) {// 如果该相邻单词还未被访问过if (!distance.containsKey(neighbor)) {distance.put(neighbor, currentDistance + 1);if (neighbor.equals(endWord)) {foundEnd = true;} else {queue.offer(neighbor);}}// 如果该相邻单词的距离等于当前单词的距离加 1if (distance.get(neighbor) == currentDistance + 1) {graph.computeIfAbsent(neighbor, k -> new ArrayList<>()).add(currentWord);}}}if (foundEnd) {break;}}// 回溯构建路径List<String> path = new ArrayList<>();path.add(endWord);backtrack(endWord, beginWord, graph, path, result);return result;}// 生成所有可能的相邻单词private List<String> getNeighbors(String word, Set<String> wordSet) {List<String> neighbors = new ArrayList<>();char[] chars = word.toCharArray();for (int i = 0; i < chars.length; i++) {char originalChar = chars[i];for (char c = 'a'; c <= 'z'; c++) {if (c == originalChar) {continue;}chars[i] = c;String newWord = new String(chars);if (wordSet.contains(newWord)) {neighbors.add(newWord);}}chars[i] = originalChar;}return neighbors;}// 回溯构建路径private void backtrack(String word, String beginWord, Map<String, List<String>> graph, List<String> path, List<List<String>> result) {if (word.equals(beginWord)) {List<String> newPath = new ArrayList<>(path);Collections.reverse(newPath);result.add(newPath);return;}List<String> prevWords = graph.get(word);if (prevWords != null) {for (String prevWord : prevWords) {path.add(prevWord);backtrack(prevWord, beginWord, graph, path, result);path.remove(path.size() - 1);}}}public static void main(String[] args) {WordLadderII solution = new WordLadderII();String beginWord = "hit";String endWord = "cog";List<String> wordList = Arrays.asList("hot", "dot", "dog", "lot", "log", "cog");List<List<String>> result = solution.findLadders(beginWord, endWord, wordList);for (List<String> path : result) {System.out.println(path);}}
}

代码说明：

1. findLadders 方法：

   • 首先将 wordList 转换为 HashSet 以提高查找效率。
   • 使用 graph 存储每个单词到其前一个单词的映射，distance 存储从 beginWord 到每个单词的最短距离。
   • 进行广度优先搜索，生成所有可能的相邻单词，并更新 distance 和 graph。
   • 当找到 endWord 时，调用 backtrack 方法回溯构建路径。

2. getNeighbors 方法：

   • 生成当前单词的所有可能相邻单词，通过将每个位置的字母替换为其他字母，并检查是否在 wordSet 中。

3. backtrack 方法：

   • 从 endWord 开始回溯，根据 graph 中的映射构建路径，当回溯到 beginWord 时，将路径反转并添加到结果列表中。