day72（1.31）——leetcode面试经典150

433. 最小基因变化

433. 最小基因突变

这里我一开始弄错了，我直接一开始就将s标记好，但是我发现这样有的样例是过不了的，因为只有有效突变才能作为标记成已经访问

题目：

题解：

class Solution { public int minMutation(String startGene, String endGene, String[] bank) { //先用映射将基因库中的序列赋值，方便寻找 Map<String, Integer> map = new HashMap<>(); for(int i=0;i<bank.length;i++) { map.put(bank[i], 1); } Queue<String> queue = new LinkedList<>(); queue.offer(startGene); int step = 0; while(queue.size()>0) { int size = queue.size(); for(int l=0;l<size;l++) { String t = queue.poll(); //判断一下跟最终需要的结果是否一样 if(t.equals(endGene)) { return step; } for(int i=0;i<bank.length;i++) { String s = bank[i]; if(map.get(s)==0) { continue; } int diff = 0; for(int j=0;j<s.length();j++) { if(s.charAt(j)!=t.charAt(j)) { diff++; } } if(diff==1) { queue.offer(s); //只有有效突变才能将s标记为已访问 map.put(s, 0); } } } //进行新增更改次数 step++; } return -1; } }