首页 > 编程语言 >单词接龙(JAVA)

单词接龙(JAVA)

时间:2023-10-25 17:44:43浏览次数:40  
标签:JAVA String get int 单词 接龙 wordId word dis

class Solution {
    Map<String, Integer> wordId = new HashMap<String, Integer>();  //哈希图,用于广度优先搜索
    List<List<Integer>> edge = new ArrayList<List<Integer>>();      //哈希图的邻接表,嵌套的两个一维数组组成的二维数组,
                                                                    //外层一维数组的每个元素都能映射出一个一维数组用于指明相连接的节点
    int nodeNum = 0;   //节点数量

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {          //计算路径长度的主功能函数
        for (String word : wordList) {
            addEdge(word);
        }
        addEdge(beginWord);
        if (!wordId.containsKey(endWord)) {
            return 0;
        }
        int[] dis = new int[nodeNum];
        Arrays.fill(dis, Integer.MAX_VALUE);
        int beginId = wordId.get(beginWord), endId = wordId.get(endWord);
        dis[beginId] = 0;

        Queue<Integer> que = new LinkedList<Integer>();
        que.offer(beginId);
        while (!que.isEmpty()) {
            int x = que.poll();
            if (x == endId) {
                return dis[endId] / 2 + 1;
            }
            for (int it : edge.get(x)) {
                if (dis[it] == Integer.MAX_VALUE) {
                    dis[it] = dis[x] + 1;
                    que.offer(it);
                }
            }
        }
        return 0;
    }

    public void addEdge(String word) {      //添加单词相关连结点的函数
        addWord(word);
        int id1 = wordId.get(word);
        char[] array = word.toCharArray();
        int length = array.length;
        for (int i = 0; i < length; ++i) {
            char tmp = array[i];
            array[i] = '*';
            String newWord = new String(array);
            addWord(newWord);
            int id2 = wordId.get(newWord);
            edge.get(id1).add(id2);
            edge.get(id2).add(id1);
            array[i] = tmp;
        }
    }

    public void addWord(String word) {
        if (!wordId.containsKey(word)) {
            wordId.put(word, nodeNum++);
            edge.add(new ArrayList<Integer>());
        }
    }
}

标签:JAVA,String,get,int,单词,接龙,wordId,word,dis
From: https://www.cnblogs.com/Radioactive/p/17787780.html

相关文章

  • Java基础 序列化流和反序列化流的 三个使用细节
    细节一:如果说一个类实现了Serializable接口,表示这个类的对象是可被序列化的,Java底层会根据这个类里面所有的内容进行计算,计算出一个long类型的序列号(或版本号)。假设计算出来的版本号是1,当我创建了一个这个类的对象的时候,在对象里面就包含了版本号1,用序列化流写到本地文......
  • 基于html5+javascript技术开发的房贷利率计算器,买房的码农们戳进来
    房贷计算器是一款专为购房者设计的实用工具应用,其主要功能是帮助用户详细计算房贷的还款金额、利息以及还款计划等。通过这款软件,用户可以更加便捷地了解到自己的还款情况和计划,从而更好地规划自己的财务。下面将对房贷计算器进行详细的介绍。体验地址房贷计算器体验地址关键......
  • JavaScript树型数据与一维数组相互转换方式
     /***@description一维数组转树形数据**/exportconstarrToTree=(data=[],conf={})=>(((data,{id='id',parentId='parentId',children='children'})=>{letresult=[]if(!Array.isArray(data)){r......
  • Java基础 序列化流、反序列化流
     序列化流是高级流,也是用来包装基本流的序列化流属于字节流的一种,负责输出数据;反序列化流负责输入数据 序列化流可以把Java中的对象写到本地文件中。但是写到文件中的数据我们看不懂,可以通过反序列化流把数据正确读取出来序列化流也叫对象操作输出流  序列......
  • JavaScript 中的深度克隆
    JavaScript中的深度克隆涉及创建一个新对象,该对象是现有对象的副本,并将复制延续到所有嵌套属性,以确保两个对象完全独立。这项技术对于保持程序中的不变性等任务至关重要,对于处理React等框架中的状态尤其重要。它有助于防止意外的对象突变可能引起的错误,从而产生更易于维护且无......
  • java的Long类型进行比较
    在Java中,对于Long类型的对象,如果它们包含的值在范围[-128,127]之间,它们会被缓存,以便在整数范围内进行重用。这是因为Java的自动装箱(autoboxing)机制的一部分。 问题:long类型127的比较 Long类型129的比较 如果你想在[-128,127]之外进行值的比较,而不是引用的比较,你应该使......
  • java DiffUtils文本差异对比实现
    1、首先引入mvn<dependency><groupId>io.github.java-diff-utils</groupId><artifactId>java-diff-utils</artifactId><version>4.11</version></dependency><dependency><groupId>org.apache.poi</......
  • 基于Java的垃圾分类管理系统
    (文章目录)具体实现截图主要功能:基于java(ssm)垃圾分类管理系统系统分为小区和管理员两个角色小区的主要功能有:1.小区管理者登陆系统2.垃圾分类信息查看3.垃圾站信息查看4.垃圾运输信息查看5.小区管理者在线报修申请,删除,修改,查询报修信息6.小区管理员在线投诉,删除,修改,查......
  • java MAP集合
    javaMAP集合map集合的特点有哪些?map集合是无序的,键值对,建不能重复,值可以重复,集合中的键可以为空如何给map集合赋值?可以调用map.put()方法,进行赋值(注意!键不可以重复)如何获取到map集合的值?可以调用map.get()方法,可以通过键获取值运行结果如何遍历map集合?便利map集合的......
  • Java拾贝第十一天——IO之File类
    Java拾贝不建议作为0基础学习,都是本人想到什么写什么Java中提供了IO以操控计算机中的文件File类在整个IO包中,与文件相关的类就是File类。使用它可以进行创建或删除文件因为File类是个普通类,初始化它需要调用其有参构造publicFile(Stringpathname){//传参为文件路径}使......