JAVA实现BFS

最短路径问题常用BFS或者DP。
本题用BFS。
首先构造节点-> String 和 dis
其次放入队列中 遍历
这应该也是BFS比较通用的模板

import java.util.*;

public class Change {
    public boolean[] b ;
    public class Node{
        private String s;
        private int dis;

        public Node(String s, int dis) {
            this.s = s;
            this.dis = dis;
        }
    }
    public int countChanges(String[] dic, int n, String s, String t) {
        b = new boolean[n];
        // write code here
        for (int i = 0; i < n; i++) {
            if(s.equals(dic[i])){
                b[i] = true;
                break;
            }
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(s,0));
        while (!queue.isEmpty()){
            String flag = queue.peek().s;
            int distance = queue.peek().dis;
            if(t.equals(flag)) return distance;
            for (int i = 0; i < n; i++) {
                if(b[i] == false){
                    String str = dic[i];
                    if(isTrue(flag,str)){
                        queue.offer(new Node(str,distance + 1));
                        b[i] = true;
                    }
                }
            }
            queue.poll();
        }
        return -1;
    }

    public boolean isTrue(String s,String t){
        if(s.length() != t.length()) return false;
        int i = 0;
        int count = 0;
        while (i < s.length()){
            if(s.charAt(i) != t.charAt(i)) count++;
            i++;
        }
        if(count == 1) return true;
        return false;
    }
}