class Solution {
public:
int minMutation(string start, string end, vector<string>& bank) {
}
};
433. 最小基因变化
基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。
假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）
给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。
注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。
示例 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
提示：
start.length == 8end.length == 80 <= bank.length <= 10bank[i].length == 8start、end 和 bank[i] 仅由字符 ['A', 'C', 'G', 'T'] 组成相似题目
原站题解
python3 解法, 执行用时: 36 ms, 内存消耗: 14.9 MB, 提交时间: 2022-08-01 10:55:42
class Solution:
def minMutation(self, start: str, end: str, bank: List[str]) -> int:
if start == end:
return 0
def diffOne(s: str, t: str) -> bool:
return sum(x != y for x, y in zip(s, t)) == 1
m = len(bank)
adj = [[] for _ in range(m)]
endIndex = -1
for i, s in enumerate(bank):
if s == end:
endIndex = i
for j in range(i + 1, m):
if diffOne(s, bank[j]):
adj[i].append(j)
adj[j].append(i)
if endIndex == -1:
return -1
q = [i for i, s in enumerate(bank) if diffOne(start, s)]
vis = set(q)
step = 1
while q:
tmp = q
q = []
for cur in tmp:
if cur == endIndex:
return step
for nxt in adj[cur]:
if nxt not in vis:
vis.add(nxt)
q.append(nxt)
step += 1
return -1
python3 解法, 执行用时: 36 ms, 内存消耗: 15 MB, 提交时间: 2022-08-01 10:55:10
class Solution:
def minMutation(self, start: str, end: str, bank: List[str]) -> int:
if start == end:
return 0
bank = set(bank)
if end not in bank:
return -1
q = deque([(start, 0)])
while q:
cur, step = q.popleft()
for i, x in enumerate(cur):
for y in "ACGT":
if y != x:
nxt = cur[:i] + y + cur[i + 1:]
if nxt in bank:
if nxt == end:
return step + 1
bank.remove(nxt)
q.append((nxt, step + 1))
return -1