单词接龙_最小基因变化

单词接龙

单词接龙

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
         if(!wordList.contains(endWord)){
             //endWord不在字典中,直接返回 0;
             return 0;
         }
         int count = 1;
         //将wordList存放在 哈希表中,提供查找效率!
        HashSet<String> wordSet = new HashSet<>();
        for(String x:wordList){
            wordSet.add(x);
        }
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);//初始化队列!
         wordSet.remove(beginWord);
        while (!queue.isEmpty()){
            int size = queue.size();
            boolean flag = false;
            while (size-->0){
                //出队!
                String  poll = queue.poll();
                if(poll.equals(endWord)){
                    //匹配成功!
                    return count;
                }
                StringBuilder ret = new StringBuilder(poll);
                //改变该字符!
                for (int i = 0; i <ret.length(); i++) {
                    //复原该字符串!
                    StringBuilder str = new StringBuilder(ret);
                    for(char j ='a';j<='z';j++){//改变每一个位置的字符!
                        str.setCharAt(i,j);//将i下标的字符改成j!
                        if(wordSet.contains(str.toString())){
                            //如果在字典中,入队!
                            queue.offer(str.toString());
                            //已经使用过就在字典中移除,标记使用过!
                            wordSet.remove(str.toString());
                            flag = true;
                        }
                    }
                }
            }
            if(flag){//进行了一层操作!并且找到了对应的单词转换!
                count++;
            }
        }
        return 0;
    }
}

通过哈希表提供查找效率!

最小基因变化

最小基因变化

class Solution {
    public int minMutation(String start, String end, String[] bank) {
            //ACGT
            //将bank存放在哈希表中,提高查找效率
            HashSet<String> bankSet = new HashSet<>();
        	//HashSet<StringBuilder> bankSet = new HashSet<>(); 保存 StringBuilder contains就会匹配失败!
            for(String x:bank){
                bankSet.add(x);
            }
            int count = 0;
            char[] table ={'A','C','G','T'};//参照表!
            //初始化 
            Queue<String> queue = new LinkedList<>();
            queue.offer(start);
            while(!queue.isEmpty()){
                //处理每一层!
                int size = queue.size();
                boolean flag = false;//标记是否改变过!
                while(size-->0){
                    //出队!
                    String str = queue.poll();
                    if(str.equals(end)){//匹配成功!
                        return count;
                    }
                    for(int i = 0;i<str.length();i++){
                        //改变i位置字母!
                        //复原该字符串!
                        StringBuilder ret = new StringBuilder(str);
                        for(int j = 0;j<table.length;j++){
                            ret.setCharAt(i,table[j]);//改变!
                            if(bankSet.contains(ret.toString())){
                                //有效改变!
                                flag = true;
                                //入队!
                                queue.offer(ret.toString());
                                //标记使用过!
                                bankSet.remove(ret.toString());
                            }
                        }
                    }
                }
                //这一层有效改变!
                if(flag){
                    count++;
                }
            }
        return -1;
    }
}