搜索（三）

搜索

433.最小基因变化

class Solution433 {
    
    static char[] chars = {'A', 'C', 'G', 'T'};

    public static int minMutation(String start, String end, String[] bank) {
        Queue<String> queue = new LinkedList<>();
        queue.add(start);

        Set<String> set = new HashSet<>();
        Set<String> visited = new HashSet<>();
        visited.add(start);
        for (String s : bank) {
            set.add(s);
        }
        int step = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();

            while (size-- != 0) {
                String cur = queue.poll();
                if (cur.equals(end))
                    return step;
                for (int i = 0; i < cur.length(); i++) {
                    StringBuilder stringBuilder = new StringBuilder(cur);
                    for (int j = 0; j < chars.length; j++) {
                        stringBuilder.setCharAt(i, chars[j]);
                        if (set.contains(stringBuilder.toString()) && !visited.contains(stringBuilder.toString())) {
                            queue.offer(stringBuilder.toString());
                            visited.add(stringBuilder.toString());
                        }

                    }
                }
            }

            step++;
        }

        return -1;
    }
}

127.单词接龙

class Solution127 {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {

        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        Set<String> dict = new HashSet<>();
        for (String s : wordList) {
            dict.add(s);
        }
        int step = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();

            while (size-- != 0) {
                String curWord = queue.poll();
                if (curWord.equals(endWord)) {
                    return step;
                }

                for (int i = 0; i < curWord.length(); i++) {
                    StringBuilder stringBuilder = new StringBuilder(curWord);
                    for (char ch = 'a'; ch <= 'z'; ++ch) {
                        stringBuilder.setCharAt(i, ch);
                        String changeWord = stringBuilder.toString();
                        if (dict.contains(changeWord) && !visited.contains(changeWord)) {
                            queue.offer(changeWord);
                            visited.add(changeWord);
                        }
                    }
                }

            }
            step++;
        }

        return 0;
    }
}

752. 打开转盘锁

class Solution752 {

    public int openLock(String[] deadends, String target) {
        Set<String> deadEnds = new HashSet<>();
        for (String s : deadends) {
            deadEnds.add(s);
        }

        if (deadEnds.contains("0000"))
            return -1;
        Set<String> visited = new HashSet<>();

        Queue<String> queue = new LinkedList<>();
        queue.offer("0000");
        visited.add("0000");
        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- != 0) {
                String curWord = queue.poll();
                if (curWord.equals(target))
                    return step;
                for (int i = 0; i < curWord.length(); i++) {
                    StringBuilder tmp1 = new StringBuilder(curWord);
                    StringBuilder tmp2 = new StringBuilder(curWord);
                    char tmp1Ch = curWord.charAt(i);
                    tmp1Ch = tmp1Ch == '0' ? '9' : --tmp1Ch;
                    char tmp2Ch = curWord.charAt(i);
                    tmp2Ch = tmp2Ch == '9' ? '0' : ++tmp2Ch;
                    //判断是否在死亡数组中

                    tmp1.setCharAt(i, tmp1Ch);
                    tmp2.setCharAt(i, tmp2Ch);
                    if (!deadEnds.contains(tmp1.toString()) && !visited.contains(tmp1.toString())) {
                        queue.add(tmp1.toString());
                        visited.add(tmp1.toString());
                    }
                    if (!deadEnds.contains(tmp2.toString()) && !visited.contains(tmp2.toString())) {
                        queue.add(tmp2.toString());
                        visited.add(tmp2.toString());
                    }
                }
            }
            step++;
        }
        return -1;
    }
}