深度优先模板
/* * dfs * 终止条件 * 访问当前节点 * 下探到下一层 * visted = set() * * def(node,visited): * if node in visited: * return * * visited.add(node) * * for next_node in node.children(): * if not next_node in visited: * dfs(next.node,visited) */
题意理解：从bank中找到一条最短的路径，这条路径通往end，路径上的每个节点都是上一个节点变换一个字母得来的
/* * 题意：在bank中找到从start到end的最短路径，每次变换一个元素 * 大佬的思路： * 1.遍历bank找出与当前节点相差一个字符的元素，作为下一层的开始 * 2.当当前元素到达end时，记录当前的路径长度（层数）和原来的路径值 * （初始化为Max）中的最小值 */ public class Main { static int minStepCount = Integer.MAX_VALUE; //记录最小路径值 public static void main(String[] args) { String start = "AACCGGTT"; String end = "AAACGGTA"; String[] bank = {"AACCGGTA", "AACCGCTA", "AAACGGTA"}; HashSet<String> hs = new HashSet(); //记录当前次循环中，是否遍历过该字符串，相当于visit数组的作用 fin(0,bank,end,start,hs); //遍历bank找路径 if(minStepCount != Integer.MAX_VALUE) System.out.println(minStepCount); else System.out.println("-1"); } public static void fin(int lev,String[] bank, String end,String cur,HashSet<String> v) { if(cur.equals(end)) //当当前路径可以到达end的时候，记录最短路径长度，lev层数表示当前的路径长度 minStepCount = Math.min(minStepCount, lev); for(String str : bank) { //遍历bank，寻找下一层的开始字符串，即与当前字符串只相差一个字符的字符串 int dif = 0;//记录两个字符串的距离 for(int i = 0;i < cur.length();i++) { if(cur.charAt(i) != str.charAt(i)) { if(++dif > 1) break;//如果当前字符串和bank中的字符串相差超过1，则直接break } } if(dif == 1 && !v.contains(str)) {//当当前字符串月遍历到的字符串相差为1个字符时 //还需要判断是否之前访问过该字符串，如果没有访问过，则添加到set中 v.add(str); fin(lev+1,bank,end,str,v);//以遍历到的字符串作为开始字符串进行递归，并且层数加一 v.remove(str); //当递归返回时。移走访问过的字符串，因为从该节点向下延伸的路径已经遍历完毕 } } } }
