思路比较简单

  • 就是以基因序列为点，以找一个字母变一下为变。求点层数。

  • 属于思路很定点的BFS题目，直接看完整注释就行

    1. class Solution {
    2.   public int minMutation(String start, String end, String[] bank) {
    4.       //把基因库数组存入哈希表，以方便查找
    5.       Set<String> bankSet = new HashSet<String>(Arrays.asList(bank));
    6.       //用来记录一个基因，是从start 开始，变了多少步骤
    7.       Map<String,Integer> depthMap = new HashMap<>();
    8.       //记录一下子标准基因
    9.        char[] jiyins  = {'A', 'C', 'G', 'T'};
    10.       //如果end不合法不在基因库直接返回
    11.       if(!bankSet.contains(end)){
    12.           return -1;
    13.       }
    14.       //广搜BFS需要使用队列
    15.       Queue<String> queue = new LinkedList<>();
    16.       //先把start放入队列中去
    17.       queue.add(start);
    18.       //执行BFS标准广搜
    19.       while (!queue.isEmpty()){
    20.           //队头出队，拿到一个当前基因
    21.           String oneJiyin = queue.poll();
    22.           //因为基因是8个字母，所以从每一个字母开始，向额外的三个字母开始扩展，变变化
    23.           //八个字母，所以循环8次，把每一个字母都尝试变一次
    24.           for(int i = 0; i < 8; i++){
    25.               //遍历合法基因字母，一共四个，去向着除了自己的那个，剩下的三个方向扩展
    26.               for(char jy : jiyins){
    27.                   //在这里才转换数组，是因为每一次要使用新的值，这一次改变不能把原值替换掉，换过方向的要是新对象
    28.                   char[] jiyinChars = oneJiyin.toCharArray();
    29.                   if(jiyinChars[i] != jy){
    30.                       //找到一个新的可替换的值，就进行替换
    31.                       jiyinChars[i] = jy;
    32.                       //然后入队列，并且保存深度。深度等于原深度+1
    33.                       String newJiyin = new String(jiyinChars);
    34.                       //如果新的基因，不在基因库里，则继续搜索，忽略这个新基因
    35.                       if(!bankSet.contains(newJiyin)){
    36.                           continue;
    37.                       }
    38.                       //如果基因深度记录器，已经有过这个新基因了，说明这个新基因出现过了，那就忽略这个新基因
    39.                       if(depthMap.containsKey(newJiyin)){
    40.                           continue;
    41.                       }
    42.                       queue.add(newJiyin);
    43.                       depthMap.put(newJiyin,depthMap.getOrDefault(oneJiyin,0) + 1);
    44.                       //如果这个新的基因就是end结果，那么返回其深度。也就是最终变化了多少次
    45.                       if(newJiyin.equals(end)){
    46.                           return depthMap.get(newJiyin);
    47.                       }
    48.                   }
    49.               }
    51.           }
    53.       }
    54.       //如果start无法转换成end 返回-1
    55.       return -1;
    56.   }
    57. }