BFS
leetcode 最小基因變化
寬度優先搜索一般會結合佇列
- java實作
class Solution {
public int minMutation(String start, String end, String[] bank) {
// 定義三個集合，分別是合法基因集合，起始基因集合，目標基因集合，起始基因記憶集，目標基因記憶集
Set<String> 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<String> st, Set<String> ed, Set<String> menSt, Set<String> menEd, Set<String> dict, int len) {
// 起始集合為空，那么就無法到達目標
if(st.size() == 0) return -1;
// 優先從數量少的一端開始搜索，減少搜索量
if(st.size() > ed.size()) return bfs(ed, st, menEd, menSt, dict, len);
Set<String> 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
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/378650.html
標籤：其他
上一篇：python獲取日期相關方法
下一篇：conda使用