Java算法题-解析单词接龙问题 II
在这个算法题中，我们将探讨如何找到从起始单词到目标单词的所有最短转换路径，而且要求每个转换路径都是唯一的。
题目
单词接龙 II 是一个经典的算法问题，给定一个起始单词、一个目标单词和一个单词列表，要求找出所有从起始单词到目标单词的最短转换路径，每次只能改变一个字母。要求返回所有最短路径。
引言
这个问题可以看作是一个图搜索问题，图中的节点是单词，如果两个单词只有一个字母不同且在同样的位置，那么它们之间有一条边。因此，我们可以构建一个以起始单词为根节点的图，然后使用广度优先搜索（BFS）来遍历图，找到到达目标单词的所有最短路径。
算法思路
- 首先，我们需要使用广度优先搜索构建一个图，表示单词之间的关系。具体地，我们可以从起始单词开始，逐个改变每个位置上的字母，如果改变后的单词在单词列表中，就添加一条边。
- 我们使用一个队列来进行广度优先搜索，队列中的每个元素都是一个路径，初始时，队列中只包含起始单词构成的路径。
- 在每一轮搜索中，我们从队列中取出一个路径，然后考虑以该路径的最后一个单词为起点，改变一个字母后得到的单词，如果该单词在图中存在，就将这个新的单词添加到路径中，并将路径重新放入队列中。
- 如果在搜索过程中找到目标单词，就将该路径添加到结果列表中。
- 最终，当队列为空或者找到了目标单词后，搜索结束，返回结果列表。
代码实现
以下是使用 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<>();
Set<String> wordSet = new HashSet<>(wordList);
if (!wordSet.contains(endWord)) {
return result;
}
Map<String, List<String>> graph = new HashMap<>();
Map<String, Integer> distance = new HashMap<>();
List<String> path = new ArrayList<>();
path.add(beginWord);
buildGraph(beginWord, endWord, graph, distance, wordSet);
dfs(beginWord, endWord, graph, distance, path, result);
return result;
}
private void buildGraph(String beginWord, String endWord, Map<String, List<String>> graph, Map<String, Integer> distance, Set<String> wordSet) {
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
distance.put(beginWord, 0);
for (String word : wordSet) {
graph.put(word, new ArrayList<>());
}
while (!queue.isEmpty()) {
int size = queue.size();
boolean foundEndWord = false;
Set<String> visitedThisLevel = new HashSet<>();
for (int i = 0; i < size; i++) {
String currentWord = queue.poll();
int currentDistance = distance.get(currentWord);
char[] wordChars = currentWord.toCharArray();
for (int j = 0; j < wordChars.length; j++) {
char originalChar = wordChars[j];
for (char c = 'a'; c <= 'z'; c++) {
if (c == originalChar) {
continue;
}
wordChars[j] = c;
String nextWord = new String(wordChars);
if (wordSet.contains(nextWord)) {
graph.get(currentWord).add(nextWord);
if (!distance.containsKey(nextWord)) {
distance.put(nextWord, currentDistance + 1);
if (nextWord.equals(endWord)) {
foundEndWord = true;
} else {
queue.offer(nextWord);
visitedThisLevel.add(nextWord);
}
}
}
}
wordChars[j] = originalChar;
}
}
if (foundEndWord) {
break;
}
wordSet.removeAll(visitedThisLevel);
}
}
private void dfs(String currentWord, String endWord, Map<String, List<String>> graph, Map<String, Integer> distance, List<String> path, List<List<String>> result) {
if (currentWord.equals(endWord)) {
result.add(new ArrayList<>(path));
return;
}
for (String nextWord : graph.get(currentWord)) {
if (distance.get(nextWord) == distance.get(currentWord) + 1) {
path.add(nextWord);
dfs(nextWord, endWord, graph, distance, path, result);
path.remove(path.size() - 1);
}
}
}
}算法分析
- 时间复杂度：在最坏情况下，需要遍历单词列表中的所有单词，每个单词都需要检查其所有可能的变换，因此时间复杂度为 O(M * N)，其中 M 是单词的长度，N 是单词列表中的单词数量。
- 空间复杂度：需要额外的空间来存储单词集合、队列、图等数据结构，空间复杂度为 O(N)。
示例和测试
我们可以使用以下代码进行测试：
public class Main {
public static void main(String[] args) {
WordLadderII solution = new WordLadderII();
String beginWord = "hit";
String endWord = "cog";
List<String> wordList = new ArrayList<>(Arrays.asList("hot", "dot", "dog", "lot", "log", "cog"));
List<List<String>> shortestPaths = solution.findLadders(beginWord, endWord, wordList);
for (List<String> path : shortestPaths) {
System.out.println("最短路径: " + path);
}
}
}总结
单词接龙 II 是一个复杂的图搜索问题，要求找到所有最短路径。通过构建单词之间的关系图，并使用广度优先搜索和深度优先搜索，我们可以有效地解决这个问题。这个问题的时间复杂度是 O(M * N)，空间复杂度是 O(N)，其中 M 是单词的长度，N 是单词列表中的单词数量。理解图搜索算法对于解决类似的问题非常有帮助。
