Java最小基因变化leetcode

        基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。

        假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

        例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。
        另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。

        给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。

        注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。

class Solution {
	char[] a = new char[] { 'A', 'C', 'G', 'T' };

	public int minMutation(String start, String end, String[] bank) {
		int len = bank.length;

        //bank中对应位置的元素是否已经使用过（是否添加进队列）
		boolean[] used = new boolean[len];

        //如果end不是有效序列，则返回-1
		Map hash = new HashMap<>();
		for (int i = 0; i < len; i++) {
			hash.put(bank[i], i);
		}
		if (!hash.containsKey(end)) {
			return -1;
		}

		Queue queue = new LinkedList<>();
        //第一位
		queue.add(new int[] { -1, 0 });

		while (!queue.isEmpty()) {
			int[] cur = queue.poll();

            //cur[0]为bank中序列的编号
            //如果是-1则是start，其他则是对应编号的bank中序列
			char[] cs = cur[0] == -1 ? start.toCharArray() : bank[cur[0]].toCharArray();
            //接下来的操作距离+1
			int dist = cur[1] + 1;

            //每一位遍历
            //能通过一步变成bank中的序列的都加入队列
			for (int i = 0; i < 8; i++) {
				char replace = cs[i];
				
                for (int j = 0; j < 4; j++) {
					cs[i] = a[j];

                    //如果这个字符串是bank中的一员，则返回它的编号，否则返回-1
					String tmp = new String(cs);
					int idx = hash.getOrDefault(tmp, -1);

                    //不为-1则编号存在，并且没有被使用过时
					if (idx != -1 && !used[idx]) {
                        //如果是目标end，返回距离
						if (tmp.equals(end)) {
							return dist;
						}
						queue.add(new int[] { idx, dist });
						used[idx] = true;
					}
				}
				
                cs[i] = replace;
			}
		}
		return -1;
	}
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：39.1 MB, 在所有 Java 提交中击败了75.64%的用户