Java算法题-解析单词接龙问题 II
![](https://wx.javatiku.cn/j/j301-t.jpg)
在这个算法题中,我们将探讨如何找到从起始单词到目标单词的所有最短转换路径,而且要求每个转换路径都是唯一的。
题目
单词接龙 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 是单词列表中的单词数量。理解图搜索算法对于解决类似的问题非常有帮助。