力扣127-白红宇

力扣127

阅读量：175 次

发布时间：2019-02-28

本文共 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/

你可能感兴趣的文章