22.对于BFS的思考

由两道力扣题来引出此篇内容:

单词演变

算法思路:

• 将每个单词抽象为一个点,如果两个单词可以只改变一个字母进行变换,那么说明他们之间有一条双向边,因此把满足转换条件的点相连,就形成了一张图
• 但是如果枚举每一对单词的组合,来判断他们是否相差一个字符,这样的效率太低了,我们可以创建邻接的虚拟节点,比如hit的虚拟节点为*it,h*t和hi*,这三个虚拟节点直接和hit节点相连,如果一个单词能转化为hit,那么它就会连接到虚拟节点上去
• 在最后计算长度的时候,我们计算的距离由于有虚拟节点的贡献,所以最终的长度会为原来长度的两倍
• 由于beginword也算在距离内,所以在初始化距离时,因为beginword也有虚拟节点,本应初始化为1的距离,现在初始化为2

    private List<List<Integer>> edges;
    int curId = 0;
    
    Map<String, Integer> map = new HashMap<>();//String到id的映射

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //图的构建过程
        edges = new ArrayList<>();
        addEdge(beginWord);
        for (String s : wordList) {
            addEdge(s);
        }
        //特殊情况
        if (!map.containsKey(endWord)) return 0;
        //起始id和终止id
        Integer startId = map.get(beginWord);
        Integer endId = map.get(endWord);
        //用于记录每个id对应的距离
        int[] distance = new int[curId];
        //初始化为MAX后判断是否为MAX再继续算法,具有排重作用
        Arrays.fill(distance, Integer.MAX_VALUE);
        //初始化startId
        distance[startId] = 2;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(startId);
        while (!queue.isEmpty()){
            Integer cur = queue.poll();
            //找到结果
            if(cur.equals(endId))return distance[cur]/2;
            for (Integer edge : edges.get(cur)) {
                //当distance第一次被初始化的时候才使用
                if(distance[edge]==Integer.MAX_VALUE){
                    distance[edge]=distance[cur]+1;
                    queue.offer(edge);
                }
            }
        }
        return 0;
    }

    
    //添加连接关系和虚拟节点
    private void addEdge(String s) {
        addWord(s);
        StringBuilder sb = new StringBuilder(s);
        Integer id1 = map.get(sb.toString());
        for (int i = 0; i < sb.length(); i++) {
            char c = sb.charAt(i);
            sb.setCharAt(i, '*');
            addWord(sb.toString());
            Integer id2 = map.get(sb.toString());
            edges.get(id1).add(id2);
            edges.get(id2).add(id1);
            sb.setCharAt(i, c);
        }
    }

    //增加字符串到映射关系和初始化边
    private void addWord(String s) {
        //当有重复节点的情况,保留之前的节点编号
        if (map.containsKey(s)) return;
        map.put(s, curId++);
        edges.add(new ArrayList<>());
    }

 开密码锁

此题看上去和上题极为相似,其实思路并不相同,第一题其实是提前建立图,然后对图进行bfs搜索得到最短距离,这题如果使用提前建立图的方法,所建立的图的大小拥有10000个节点,可是有些节点我们根本用不到,所以对于此题并没有建图的过程

public int openLock(String[] deadends, String target) {
        Set<String> deadMap = new HashSet<>(Arrays.asList(deadends));
        //特判
        if (deadMap.contains("0000")) return -1;
        if (target.equals("0000")) return 0;

        Set<String> used = new HashSet<>();

        Queue<String> queue = new LinkedList<>();
        queue.add("0000");
        int step = 0;
        while (!queue.isEmpty()) {
            //step加一步代表bfs过一轮,也就是距离+1
            int size = queue.size();
            ++step;
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                for (String neighbor : getNeighbor(cur)) {
                    if (neighbor.equals(target)) return step;
                    //需要对deadMap和used进行排重,使用过的就不在考虑范围内了
                    if (!deadMap.contains(neighbor) && !used.contains(neighbor)) {
                        used.add(neighbor);
                        queue.add(neighbor);
                    }
                }
            }
        }
        return -1;
    }
    //获得该字符串所有可能的下一步状态
    private List<String> getNeighbor(String s) {
        StringBuilder sb = new StringBuilder(s);
        List<String> res = new ArrayList<>();
        for (int i = 0; i < sb.length(); i++) {
            char temp = sb.charAt(i);
            char la = getLastChar(temp);
            char ne = getNextChar(temp);
            sb.setCharAt(i, la);
            res.add(sb.toString());
            sb.setCharAt(i, ne);
            res.add(sb.toString());
            sb.setCharAt(i, temp);
        }
        return res;
    }

    private char getNextChar(char c) {
        return c == '9' ? '0' : ++c;
    }

    private char getLastChar(char c) {
        return c == '0' ? '9' : --c;
    }