给定两个字符串,记为start和to,再给定一个字符串列表list,list中一定包含to,list中没有重复的字符串。所有的字符串都是小写的。规定start每次只能改变一个字符,最终的目标是彻底变成to,但是每次变成新字符串必须在list中存在。请返回所有的最短的变换路径(按照字典序最小的顺序输出)。
输出包含多行,第一行包含一个整数n,代表list的中字符串的个数,第二行中包含两个字符串,分别代表start和to。接下来n行,每行一个字符串,代表lis[i](保证字符串长度都为3)。
如果存在转换的路径,请先输出“YES”,然后按照字典序最小的顺序输出所有路径。如果不存在请输出“NO”。
8 abc cab cab acc cbc ccc cac cbb aab abb
YES abc -> abb -> aab -> cab abc -> abb -> cbb -> cab abc -> cbc -> cac -> cab abc -> cbc -> cbb -> cab
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"); } } }