leetcode 最小基因变化
宽度优先搜索一般会结合队列
- java实现
class Solution {
public int minMutation(String start, String end, String[] bank) {
// 定义三个集合，分别是合法基因集合，起始基因集合，目标基因集合，起始基因记忆集，目标基因记忆集
Set dict = new HashSet<>(), st = new HashSet<>(), ed = new HashSet<>(), menSt = new HashSet<>(), menEd = new HashSet<>();
for(String s : bank) dict.add(s);
// 基因库中不包含目标，则无法转换
if(!dict.contains(end)) return -1;
st.add(start);
ed.add(end);
// 宽搜
return bfs(st, ed, menSt, menEd, dict, 0);
}
// 宽搜
private int bfs(Set st, Set ed, Set menSt, Set menEd, Set dict, int len) {
// 起始集合为空，那么就无法到达目标
if(st.size() == 0) return -1;
// 优先从数量少的一端开始搜索，减少搜索量
if(st.size() > ed.size()) return bfs(ed, st, menEd, menSt, dict, len);
Set next = new HashSet<>();
char[] mode = {'A', 'C', 'G', 'T'};
// 枚举起始集合可以一步转换的所有基因序列
for(String s : st) {
StringBuilder temp = new StringBuilder(s);
for(int i = 0; i < 8; i++) {
for(int j = 0; j < 4; j++) {
temp.setCharAt(i, mode[j]);
String cur = temp.toString();
// 终点集合中包含了当前字符，那么直接返回步数
if(ed.contains(cur)) return len + 1;
// 如果搜过了该种情况，就不能重复遍历
if(menSt.contains(cur)) continue;
// 如果是合法序列，则加入下一个搜索集合中
if(dict.contains(cur)) {
next.add(cur);
menSt.add(cur);
}
temp.setCharAt(i, s.charAt(i));
}
}
}
// 搜索下一层
return bfs(next, ed, menSt, menEd, dict, len + 1);
}
}
- python实现
class Solution:
def minMutation(self, start: str, end: str, bank: List[str]) -> int: #-> int :提示返回值类型
B = ['A', 'C', 'G', 'T']
queue = [start]
vis = set() #记忆已经搜索过的序列
step = 0
# 开始宽度优先搜索
while queue:
size = len(queue)
for i in range(size):
cur = queue.pop(0)
if cur == end:
return step
for i in range(len(cur)):
for j in B:#改变每一个基因形成新的基因序列靠经目标基因
s = cur[:i] + j + cur[i + 1:]
if s in bank and s not in vis:
queue.append(s)
vis.add(s)
step += 1
return -1
