力扣127-白红宇

力扣127

阅读量：175 次

发布时间：2019-02-28

本文共 2818 字，大约阅读时间需要 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/

你可能感兴趣的文章