LeetCode——433.最小基因变化

通过万岁！！！

• 题目：就是给你一个start的字符串，然后每次变换一个字符，要求变换到end字符，并且中途的变化中，都要求在bank这个数组中。
• 思路：
  • 其实就是一个路径的问题，这里就是从某一点开始，然后经过bank中的路径，怎么样能最快到达end。看到路径最短，其实就是用广度优先就可以了。
  • 跟蓝桥杯的跳马问题优点相似。但是唯一的不同就是，这里的第几层怎么确定。有一个常规的做法，就是我们把上一层的长度保存下来，上一层的长度就是队列的长度。
  • 注意，这里一定要将长度保存下来，然后用fori遍历，因为我们会修改这个队列。
  • 还有就是剪枝了，这里如果这个bank的字符串我们用过了，则就需要标记一下，只有没有用过，我们才需要变成这个字符。并且还需要判断bank中有没有这个字符串，所以我们可以定义一个map，map的key是这个字符串，然后value是这个字符串的下标，然后定义一个vis数组，标记这个字符串是不是遍历过。
• 技巧：这里既然是bfs，那么就需要用到队列了。

java代码

class Solution {
    public int minMutation(String start, String end, String[] bank) {
        StringBuilder startSB = new StringBuilder(start);
        StringBuilder endSB = new StringBuilder(end);
        Map map = new HashMap<>();
        int len = bank.length;
        boolean[] vis = new boolean[len];
        char[] chars = {'A', 'C', 'G', 'T'};


        for (int i = 0; i < len; i++) {
            map.put(bank[i], i);
        }
        Queue queue = new LinkedList<>();
        queue.add(start);// 这个不用在vis中
        int ans = 0;
        while (!queue.isEmpty()) {
            // 要把这个队列中的内容都遍历完，才算是一层
            int queueSize = queue.size();// 这里一定要取出来，给一个变量
            for (int k = 0; k < queueSize; k++) {
                String poll = queue.poll();
                if (poll.equals(end)) {
                    return ans;
                }
                for (int i = 0; i < 8; i++) {// 位置
                    for (int j = 0; j < 4; j++) {// 字符
                        StringBuilder pollSB = new StringBuilder(poll);// 接下来对poll的第i位置进行转换
                        pollSB.setCharAt(i, chars[j]);
                        // 下面用到pollSB的String形式
                        String pollStr = pollSB.toString();
                        if (map.containsKey(pollStr) && !vis[map.get(pollStr)]) {
                            vis[map.get(pollStr)] = true;// 已经变成这个了
                            queue.add(pollStr);
                        }
                    }
                }
            }
            ans++;
        }
        return -1;
    }
}

• 总结：题目比较有意思，主要是这里怎么找第几层，方法是通过保存queue的长度进行的，非常关键。