IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> Java知识库 -> 单词演变java实现 -> 正文阅读

[Java知识库]单词演变java实现

方法一:两个队列遍历

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //创建两个队列,用于交替遍历当前单词变化一个字母之后可以得到的单词
        Queue<String> queue1 = new LinkedList<>();
        Queue<String> queue2 = new LinkedList<>();
        //创建一个集合用于存储字典中的单词,每当遍历过字典中的一个单词就删除
        HashSet<String> set = new HashSet<>(wordList);
        //初始化队列1以及步长
        int step = 1;
        queue1.offer(beginWord);
        //开始遍历queue1
        while(!queue1.isEmpty()){
            //从queue1中取出一个单词
            String pos = queue1.poll();
            //如果这个单词就是我们要找的目标单词直接退出循环返回结果
            if(pos.equals(endWord)){
                return step;
            }
            //获取pos变化一个字符所能得到的所有单词
            List<String> neighbor = getNeighbor(pos);
            //遍历这些单词,如果有单词存在set中就,说明现在字典中的这个单词还没有被访问过需要加入到queue2中进行下一步的遍历
            for(String str : neighbor){
                if(set.contains(str)){
                    queue2.offer(str);
                    set.remove(str);
                }
            }
            //判断queue1是否为空,如果为空交换queue1和queue2继续遍历下一个步长的单词
            if(queue1.isEmpty()){
                queue1 = queue2;
                queue2 = new LinkedList<>();
                step++;
            }
        }
        //当所有的单词全部遍历结束之后如果还没有找到,说明字典中根本就不存在这样一种变化
        return 0;
    }

    private List<String> getNeighbor(String str){
        //将当前的单词转化为Char数组
        char[] strChar = str.toCharArray();
        List<String> result = new LinkedList<>();
        //循环char数组的每一个位置
        for(int i = 0;i < strChar.length;i++){
            char old = strChar[i];
            //改变每一个位置的值添加到结果中,需要略过原本的字符
            for(char c = 'a';c <= 'z';c++){
                if(c != old){
                    strChar[i] = c;
                    result.add(new String(strChar));
                }
            }
            //当添加结束之后需要还原原字符
            strChar[i] = old;
        }
        //返回结果集合
        return result;
    }
}

方法二:双向广度优先搜索

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //创建三个set分别用于表示未访问过的节点,从初始节点出发下一次需要访问的节点,从尾节点出发下一次需要访问的节点
        Set<String> notVisited = new HashSet<>(wordList);
        if(!notVisited.contains(endWord)){
            return 0;
        }
        Set<String> set1 = new HashSet<>();
        set1.add(beginWord);
        notVisited.remove(beginWord);
        Set<String> set2 = new HashSet<>();
        set2.add(endWord);
        notVisited.remove(endWord);
        int step = 2;
        //保证两个集合都不为空的情况下遍历,只要有一个集合空了说明永远无法相遇了
        while(set1.size() != 0 && set2.size() != 0){
            //保证set1是较少元素的集合,我们遍历较少元素的集合到较多元素的集合中去比对这样可以减少遍历的节点数量
            if(set1.size() > set2.size()){
                Set<String> temp = new HashSet<>();
                temp = set1;
                set1 = set2;
                set2 = temp;
            }
            Set<String> set3 = new HashSet<>();
            //遍历set1中的所有节点找出它们变换一个字符之后的节点是否存在set2中如果存在则说明相遇遍历结束
            //如果不存在但是未遍历过就将其放入set3在下一次遍历的时候使用
            for(String str : set1){
                List<String> neighbor = getNeighbor(str);
                for(String s : neighbor){
                    if(set2.contains(s)){
                        return step;
                    }
                    if(notVisited.contains(s)){
                        set3.add(s);
                        notVisited.remove(s);
                    }
                }
            }
            //当set1位空替换set1和set3继续遍历
            set1 = set3;
            step++;
        }
        //当所有的单词全部遍历结束之后如果还没有找到,说明字典中根本就不存在这样一种变化
        return 0;
    }

    private List<String> getNeighbor(String str){
        //将当前的单词转化为Char数组
        char[] strChar = str.toCharArray();
        List<String> result = new LinkedList<>();
        //循环char数组的每一个位置
        for(int i = 0;i < strChar.length;i++){
            char old = strChar[i];
            //改变每一个位置的值添加到结果中,需要略过原本的字符
            for(char c = 'a';c <= 'z';c++){
                if(c != old){
                    strChar[i] = c;
                    result.add(new String(strChar));
                }
            }
            //当添加结束之后需要还原原字符
            strChar[i] = old;
        }
        //返回结果集合
        return result;
    }
}
  Java知识库 最新文章
计算距离春节还有多长时间
系统开发系列 之WebService(spring框架+ma
springBoot+Cache(自定义有效时间配置)
SpringBoot整合mybatis实现增删改查、分页查
spring教程
SpringBoot+Vue实现美食交流网站的设计与实
虚拟机内存结构以及虚拟机中销毁和新建对象
SpringMVC---原理
小李同学: Java如何按多个字段分组
打印票据--java
上一篇文章      下一篇文章      查看所有文章
加:2021-12-04 13:15:32  更:2021-12-04 13:21:21 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/29 14:39:32-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码