本文共 2753 字，大约阅读时间需要 9 分钟。
为了解决这个问题，我们需要在给定的字典中找到一个单词，使其与给定的单词只相差一个字母，并找到最短的转换路径。我们可以使用图的广度优先搜索（BFS）方法来实现这一点。
问题分析：我们需要找到一个单词，使其与给定的单词只相差一个字母。如果存在这样的单词，我们需要找到最短的转换路径。
图的表示：将每个单词视为图中的一个节点，边的连接条件是两个单词只相差一个字母。
广度优先搜索（BFS）：使用BFS进行图的遍历，这样可以找到从开始单词到结束单词的最短路径。
辅助类和数据结构：使用辅助类存储单词及其层数，哈希集合记录已访问的单词，二维数组记录单词之间的转换关系。
package Leetcode;import java.util.*;public class Demo127 { class LevelWord { String word; int level; public LevelWord(String word, int level) { this.word = word; this.level = level; } } public int length2(String beginWord, String endWord, List wordList) { int endIndex = wordList.indexOf(endWord); if (endIndex == -1) { return 0; } if (!wordList.contains(beginWord)) { wordList.add(beginWord); } boolean[][] adjacencyMatrix = new boolean[wordList.size()][wordList.size()]; HashMap visited = new HashMap<>(); for (int i = 0; i < wordList.size(); i++) { for (int j = 0; j < i; j++) { if (hasPath(wordList.get(i).toCharArray(), wordList.get(j).toCharArray())) { adjacencyMatrix[i][j] = adjacencyMatrix[j][i] = true; } } visited.put(wordList.get(i), false); } Queue queue = new LinkedList<>(); queue.add(new LevelWord(beginWord, 0)); visited.put(beginWord, true); while (!queue.isEmpty()) { LevelWord temp = queue.poll(); if (temp.word.equals(endWord)) { return temp.level + 1; } int currentIndex = wordList.indexOf(temp.word); List nextWords = new ArrayList<>(); for (int i = 0; i < wordList.size(); i++) { if (adjacencyMatrix[currentIndex][i]) { nextWords.add(wordList.get(i)); } } for (String nextWord : nextWords) { if (!visited.get(nextWord)) { visited.put(nextWord, true); queue.add(new LevelWord(nextWord, temp.level + 1)); } } } return 0; } public boolean hasPath(char[] chars1, char[] chars2) { int diff = 0; for (int i = 0; i < chars1.length; i++) { if (chars1[i] != chars2[i]) { diff++; if (diff > 1) { return false; } } } return diff == 1; }} 辅助类 LevelWord：用于存储当前处理的单词及其层数，层数表示从开始单词到该单词的步骤数。
length2 方法：主要处理逻辑，包括初始化字典中的单词，创建二维数组记录转换关系，使用BFS遍历图，找到最短路径。
hasPath 方法：判断两个单词是否只相差一个字母。
BFS 遍历：从开始单词出发，逐层扩展，找到与结束单词相差一个字母的最短路径。
通过这种方法，我们可以高效地找到字典中与给定单词只相差一个字母的单词，并返回最短的转换距离。
转载地址：http://xtec.baihongyu.com/