🌕🌕 433. 最小基因变化

难度: 🌕🌕

问题描述

---

解法

class Solution {
    public int minMutation(String start, String end, String[] bank) {
        // 思路：
        // 广度优先搜索 - 双向
        ArrayList<String> list = new ArrayList<>();
        for(String str: bank) {
            list.add(str);
        }
        int index = list.indexOf(end);
        if(index < 0) {
            return -1; // end 不存在于 list 直接返回
        }
        // bfs
        LinkedList<String> headQ = new LinkedList<>();
        LinkedList<String> tailQ = new LinkedList<>();
        HashSet<String> headS = new HashSet<>();
        HashSet<String> tailS = new HashSet<>();
        headQ.offer(start);
        tailQ.offer(end);
        headS.add(start);
        tailS.add(end);
        int count = 2; // 节点数，初始已经有 2 个节点

        while(!headQ.isEmpty() && !headS.isEmpty()) {
            // 每次保证 headQ 中的元素最少，这样这一层的节点数少，属于优化范畴
            if(headQ.size() > tailQ.size()) {
                LinkedList<String> tmpQ = headQ;
                headQ = tailQ;
                tailQ = tmpQ;
                HashSet<String> tmpS = headS;
                headS = tailS;
                tailS = tmpS;
            }
            // 对 headQ 节点判断能否继续走下一步
            int len = headQ.size();
            count ++; // 先假设这一步肯定会被加入到首节点路径中

            for(int i = 0; i < len; i ++) {
                String cur = headQ.poll(); // 当前节点
                // 尝试能够往下走，即遍历 list 判断是否存在异位词
                for(String str: list) {
                    if(headS.contains(str)) {
                        continue; // 已经走过
                    }
                    if(!isValid(cur, str)) {
                        continue; // 不满足异位词条件
                    }
                    // str 是异位词 && 之前没有走过
                    // 判断终点路径是否包含该节点
                    if(tailS.contains(str)) {
                        return count - 2;
                    }
                    // 终点路径没有走过，将其加入首节点所走路径中
                    headQ.offer(str);
                    headS.add(str);
                }
            }
        }
        return -1;
    }

    private boolean isValid(String target, String str) {
        int diff = 0;
        for(int i = 0; i < target.length(); i ++) {
            if(target.charAt(i) != str.charAt(i)) {
                if(diff == 0) {
                    diff ++;
                } else {
                    return false;
                }
            }
        }
        return diff == 1;
    }
}

---

输出