字符串的转换路径问题

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void getShortPaths(String cur, String to,
                              Map<String, List<String>> nexts,
                              Map<String, Integer> distances,
                              Deque<String> path, List<List<String>> res) {
        path.add(cur);
        if (cur.equals(to)) {
            res.add(new ArrayList<>(path));
            path.pollLast();
            return;
        }
        for (String next : nexts.get(cur)) {
            if (distances.get(next) == distances.get(cur) + 1) {
                getShortPaths(next, to, nexts, distances, path, res);
            }
        }
        path.pollLast();
    }

    public static Map<String, Integer> getDistance(String from, Map<String, List<String>> nexts) {
        Map<String, Integer> distances = new HashMap<>();
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        distances.put(from, 0);
        queue.offer(from);
        visited.add(from);
        while (!queue.isEmpty()) {
            String cur = queue.poll();
            for (String s : nexts.get(cur)) {
                if (!visited.contains(s)) {
                    distances.put(s, distances.get(cur) + 1);
                    queue.offer(s);
                    visited.add(s);
                }
            }
        }
        return distances;
    }

    public static Map<String, List<String>> getNexts(List<String> words) {
        Map<String, List<String>> nexts = new HashMap<>();
        Set<String> wordSet = new HashSet<>(words);
        for (String s : words) {
            nexts.put(s, new ArrayList<>());
        }
        for (String s : words) {
            nexts.put(s, getNext(s, wordSet));
        }
        return nexts;
    }

    private static List<String> getNext(String word, Set<String> wordSet) {
        List<String> res = new ArrayList<>();
        char[] chs = word.toCharArray();
        for (char c = 'a'; c <= 'z'; c++) {
            for (int i = 0; i < word.length(); i++) {
                if (c != chs[i]) {
                    char t = chs[i];
                    chs[i] = c;
                    if (wordSet.contains(String.valueOf(chs))) {
                        res.add(String.valueOf(chs));
                    }
                    chs[i] = t;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] line = br.readLine().split(" ");
        String from = line[0];
        String to = line[1];
        List<String> words = new ArrayList<>();
        words.add(from);
        for (int i = 0; i < n; i++) {
            words.add(br.readLine());
        }
        Map<String, List<String>> nexts = getNexts(words);
        Map<String, Integer> distance = getDistance(from, nexts);
        Deque<String> path = new LinkedList<>();
        List<List<String>> res = new ArrayList<>();
        getShortPaths(from, to, nexts, distance, path, res);
        if (res.size() == 0) {
            System.out.println("NO");
            return;
        }
        System.out.println("YES");
        List<String> paths = new ArrayList<>();
        for (List<String> strs : res) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < strs.size(); i++) {
                sb.append(strs.get(i));
                if (i != strs.size() - 1) {
                    sb.append(" -> ");
                }
            }
            paths.add(sb.toString());
        }
        Collections.sort(paths);
        for (String p : paths) {
            System.out.println(p);
        }
    }
}

import java.util.*;


public class Main {

    public static HashMap<String, TreeSet<String>> graph = new HashMap<>();
    public static ArrayList<String> nodes = new ArrayList<>();
    public static HashMap<String, TreeSet<String>> pre = new HashMap<>();
    public static ArrayList<ArrayList<String>> res = new ArrayList<>();
    public static HashMap<String, Integer> distance = new HashMap<>();

    public static class Pair {
        public String id;
        public Integer distance;

        public Pair(String id, Integer distance) {
            this.id = id;
            this.distance = distance;
        }
    }

    public static Comparator<Pair> disComparator = new Comparator<Pair>() {
        @Override
        public int compare(Pair o1, Pair o2) {
            return o1.distance-o2.distance;
        }
    };

    public static Comparator<String> charComparator = new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            return o1.compareTo(o2);
        }
    };

    public static Comparator<ArrayList<String>> listComparator = new Comparator<ArrayList<String>>() {
        @Override
        public int compare(ArrayList<String> o1, ArrayList<String> o2) {
            return o1.toString().compareTo(o2.toString());
        }
    };

    public static boolean isAdjoin(String a, String b) {
        if (a.length() != b.length()) return false;
        int differentCharCnt = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                differentCharCnt++;
            }
        }
        return differentCharCnt == 1;
    }

    public static boolean isExistPath(String start, String to) {
        PriorityQueue<Pair> queue = new PriorityQueue<>(disComparator);
        queue.offer(new Pair(start, 0));
        distance.put(start, 0);
        HashSet<String> visited = new HashSet<>();
        while (!queue.isEmpty()) {
            Pair cur = queue.poll();
            if (visited.contains(cur.id)) continue;
            visited.add(cur.id);
            for (String next : graph.get(cur.id)) {
                if (!visited.contains(next)) {
                    if (distance.get(cur.id) + 1 < distance.get(next)) {
                        distance.put(next, distance.get(cur.id)+1);
                        pre.put(next, new TreeSet<>(charComparator));
                        pre.get(next).add(cur.id);
                    } else if (distance.get(cur.id) + 1 == distance.get(next)) {
                        pre.get(next).add(cur.id);
                    }
                    queue.offer(new Pair(next, distance.get(next)));
                }

            }
        }
        return distance.get(to) != Integer.MAX_VALUE;
    }

    public static void getMinPath(String start, String to, ArrayList<String> solution) {
        if (to.equals(start)) {
            solution.add(start);
            ArrayList<String> temp = new ArrayList<>();
            for (int i = solution.size()-1; i >= 0; i--) {
                temp.add(solution.get(i));
            }
            solution.remove(start);
            res.add(temp);
            return;
        }
        solution.add(to);
        for (String preNode : pre.get(to)) {
            getMinPath(start, preNode, solution);
        }
        solution.remove(to);
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        String start = input.next();
        String to = input.next();
        for (int i = 0; i < N; i++) {
            nodes.add(input.next());
        }
        nodes.add(start);

        // initialize
        for (String node : nodes) {
            graph.put(node, new TreeSet<>(charComparator));
            distance.put(node, Integer.MAX_VALUE);
        }

        // construct graph
        for (int i = 0; i < nodes.size(); i++) {
            for (int j = 0; j < nodes.size(); j++) {
                if (isAdjoin(nodes.get(i), nodes.get(j))) {
                    graph.get(nodes.get(i)).add(nodes.get(j));
                }
            }
        }
        if (isExistPath(start, to)) {
            System.out.println("YES");
            getMinPath(start, to, new ArrayList<>());
            res.sort(listComparator);
            for (ArrayList<String> path : res) {
                for (int i = 0; i < path.size(); i++) {
                    System.out.print(path.get(i));
                    if (i != path.size()-1) {
                        System.out.print(" -> ");
                    }
                }
                System.out.println();
            }
        } else {
            System.out.println("NO");
        }
    }
}