题目描述
一条基因序列由一个带有 8 个字符的字符串表示，其中每个字符都属于 "A", "C", "G", "T"中的任意一个。
假设我们要调查一个基因序列的变化。一次基因变化意味着这个基因序列中的一个字符发生了变化。
例如，基因序列由"AACCGGTT" 变化至 "AACCGGTA" 即发生了一次基因变化。
与此同时，每一次基因变化的结果，都需要是一个合法的基因串，即该结果属于一个基因库。
现在给定 3 个参数 — start, end, bank，分别代表起始基因序列，目标基因序列及基因库，请找出能够使起始基因序列变化为目标基因序列所需的最少变化次数。如果无法实现目标变化，请返回 -1。
注意：
起始基因序列默认是合法的，但是它并不一定会出现在基因库中。如果一个起始基因序列需要多次变化，那么它每一次变化之后的基因序列都必须是合法的。假定起始基因序列与目标基因序列是不一样的。
示例 1：
start: "AACCGGTT"end: "AACCGGTA"bank: ["AACCGGTA"]
返回值: 1
示例 2：
start: "AACCGGTT"end: "AAACGGTA"bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]
返回值: 2
示例 3：
start: "AAAAACCC"end: "AACCCCCC"bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]
返回值: 3
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/minimum-genetic-mutation著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
复制代码
思路分析
今天的算法每日一题是求解最小基因变化。根据题目描述，每次只可以变动一个字符，且字符都属于"A","C","G","T"。
解决最小变化，或者最短路径问题，我们通常使用 BFS 方法求解。BFS 全称是 Breadth First Search，中文名是宽度优先搜索，也叫广度优先搜索。所谓宽度优先。就是每次都尝试访问同一层的节点。 如果同一层都访问完了，再访问下一层。
解决 BFS 问题，我们一般采取队列存储每层的数据。通过队列数据的变化，逐层查找，最终返回查找层数。
下面使朴素 BFS 解法，请参考。
通过代码
class Solution { public int minMutation(String start, String end, String[] bank) { int ans = -1; List<String> bankList = Arrays.asList(bank); if (bankList.size() == 0 || !bankList.contains(end)) { return ans; }
Queue<String> queue = new LinkedList<>(); queue.offer(start); int step = 0;
Set<String> visited = new HashSet<>(); Character[] letters = new Character[]{'A', 'C', 'G', 'T'}; while (!queue.isEmpty()) { int size = queue.size(); for (int k = 0; k < size; k++) { String temp = queue.poll(); if (temp.equals(end)) { ans = step; break; } visited.add(temp);
char[] tempStringCharArray = temp.toCharArray().clone(); for (int i = 0; i < 8; i++) { for (Character letter : letters) { if (tempStringCharArray[i] != letter) { char t = tempStringCharArray[i]; tempStringCharArray[i] = letter; String nextString = new String(tempStringCharArray); tempStringCharArray[i] = t; if (visited.contains(nextString)) { continue; } if (nextString.equals(end)) { ans = step + 1; break; } if (bankList.contains(nextString)) { queue.offer(nextString); } } } } } step++; }
return ans; }}
复制代码
总结
评论