[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;
    }
}