433. Minimum Genetic Mutation
Tags:
Medium
Skills:
Graph
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tìm số bước đột biến Gen tối thiểu để biến đổi từ startGene thành endGene, mỗi lần chỉ thay đổi 1 ký tự và mỗi trạng thái trung gian phải nằm trong bank. Nếu không thể, return -1
Approach
Các bước cụ thể
Time and space complexity
Solution
1function minMutation(startGene: string, endGene: string, bank: string[]): number {
2 const bank_set = new Set(bank);
3 if (!bank_set.has(endGene)) return -1;
4 const vis: Set<string> = new Set();
5 const queue: [string, number][] = [[startGene, 0]]
6 const genes = ['A', 'C', 'G', 'T']
7 while (queue.length) {
8 const [curr, steps] = queue.shift()!;
9 if (curr === endGene) return steps;
10 for (let i = 0; i < curr.length; i++) {
11 for (const g of genes) {
12 const mutated = curr.slice(0, i) + g + curr.slice(i + 1)
13 if (bank_set.has(mutated) && !vis.has(mutated)) {
14 vis.add(mutated);
15 queue.push([mutated, steps + 1])
16 }
17 }
18 }
19 }
20
21 return -1;
22}