433. Minimum Genetic Mutation
Генетическая string может быть представлена строкой длиной 8 символов, содержащей символы 'A', 'C', 'G' и 'T'.
Предположим, нам нужно исследовать мутацию от генетической строки startGene до генетической строки endGene, где одна мутация определяется как изменение одного символа в генетической строке.
НаExemplo, "AACCGGTT" --> "AACCGGTA" является одной мутацией.
Также существует генетический банк bank, который содержит все допустимые генетические мутации. Генетическая string должна быть в банке, чтобы считаться допустимой.
given две генетические строки startGene и endGene и генетический банк bank, return минимальное количество мутаций, необходимых для мутации от startGene до endGene. Если такой мутации не существует, return -1.
Обратите внимание, что начальная string считается допустимой, поэтому она может не быть включена в банк.
Exemplo:
Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1
C# solução
correspondente/originalusing System;
using System.Collections.Generic;
public class Solution {
public int MinMutation(string start, string end, string[] bank) {
Queue<string> queue = new Queue<string>();
HashSet<string> seen = new HashSet<string>();
queue.Enqueue(start);
seen.Add(start);
int steps = 0;
while (queue.Count > 0) {
int nodesInQueue = queue.Count;
for (int j = 0; j < nodesInQueue; j++) {
string node = queue.Dequeue();
if (node == end) {
return steps;
}
foreach (char c in "ACGT") {
for (int i = 0; i < node.Length; i++) {
char[] neighborArray = node.ToCharArray();
neighborArray[i] = c;
string neighbor = new string(neighborArray);
if (!seen.Contains(neighbor) && Array.Exists(bank, b => b == neighbor)) {
queue.Enqueue(neighbor);
seen.Add(neighbor);
}
}
}
}
steps++;
}
return -1;
}
}C++ solução
rascunho automático, revisar antes de enviar#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int MinMutation(string start, string end, vector<string> bank) {
queue<string> queue = new queue<string>();
HashSet<string> seen = new HashSet<string>();
queue.Enqueue(start);
seen.push_back(start);
int steps = 0;
while (queue.size() > 0) {
int nodesInQueue = queue.size();
for (int j = 0; j < nodesInQueue; j++) {
string node = queue.Dequeue();
if (node == end) {
return steps;
}
foreach (char c in "ACGT") {
for (int i = 0; i < node.size(); i++) {
char[] neighborArray = node.ToCharArray();
neighborArray[i] = c;
string neighbor = new string(neighborArray);
if (!seen.Contains(neighbor) && Array.Exists(bank, b => b == neighbor)) {
queue.Enqueue(neighbor);
seen.push_back(neighbor);
}
}
}
}
steps++;
}
return -1;
}
}Java solução
correspondente/originalclass Solution {
public int minMutation(String start, String end, String[] bank) {
Queue<String> queue = new LinkedList<>();
Set<String> seen = new HashSet<>();
queue.add(start);
seen.add(start);
int steps = 0;
while (!queue.isEmpty()) {
int nodesInQueue = queue.size();
for (int j = 0; j < nodesInQueue; j++) {
String node = queue.remove();
if (node.equals(end)) {
return steps;
}
for (char c: new char[] {'A', 'C', 'G', 'T'}) {
for (int i = 0; i < node.length(); i++) {
String neighbor = node.substring(0, i) + c + node.substring(i + 1);
if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {
queue.add(neighbor);
seen.add(neighbor);
}
}
}
}
steps++;
}
return -1;
}
}JavaScript solução
correspondente/originalfunction minMutation(start, end, bank) {
let queue = [start];
let seen = new Set([start]);
let steps = 0;
while (queue.length > 0) {
let nodesInQueue = queue.length;
for (let j = 0; j < nodesInQueue; j++) {
let node = queue.shift();
if (node === end) {
return steps;
}
for (let c of "ACGT") {
for (let i = 0; i < node.length; i++) {
let neighbor = node.slice(0, i) + c + node.slice(i + 1);
if (!seen.has(neighbor) && bank.includes(neighbor)) {
queue.push(neighbor);
seen.add(neighbor);
}
}
}
}
steps++;
}
return -1;
}
console.log(minMutation("AACCGGTT", "AACCGGTA", ["AACCGGTA"])); // Output: 1
console.log(minMutation("AACCGGTT", "AAACGGTA", ["AACCGGTA", "AACCGCTA", "AAACGGTA"])); // Output: 2
console.log(minMutation("AAAAACCC", "AACCCCCC", ["AAAACCCC", "AAACCCCC", "AACCCCCC"])); // Output: 3Python solução
correspondente/originalfrom collections import deque
class Solution:
def minMutation(self, start: str, end: str, bank: List[str]) -> int:
queue = deque([start])
seen = set([start])
steps = 0
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node == end:
return steps
for c in "ACGT":
for i in range(len(node)):
neighbor = node[:i] + c + node[i+1:]
if neighbor not in seen and neighbor in bank:
queue.append(neighbor)
seen.add(neighbor)
steps += 1
return -1Go solução
correspondente/originalpackage main
import (
"fmt"
)
func minMutation(start string, end string, bank []string) int {
queue := []string{start}
seen := map[string]bool{start: true}
steps := 0
for len(queue) > 0 {
nodesInQueue := len(queue)
for j := 0; j < nodesInQueue; j++ {
node := queue[0]
queue = queue[1:]
if node == end {
return steps
}
for _, c := range "ACGT" {
for i := 0; i < len(node); i++ {
neighbor := node[:i] + string(c) + node[i+1:]
if !seen[neighbor] && contains(bank, neighbor) {
queue = append(queue, neighbor)
seen[neighbor] = true
}
}
}
}
steps++
}
return -1
}
func contains(bank []string, target string) bool {
for _, b := range bank {
if b == target {
return true
}
}
return false
}
func main() {
fmt.Println(minMutation("AACCGGTT", "AACCGGTA", []string{"AACCGGTA"})) // Output: 1
fmt.Println(minMutation("AACCGGTT", "AAACGGTA", []string{"AACCGGTA", "AACCGCTA", "AAACGGTA"})) // Output: 2
fmt.Println(minMutation("AAAAACCC", "AACCCCCC", []string{"AAAACCCC", "AAACCCCC", "AACCCCCC"})) // Output: 3
}Algorithm
Инициализируйте очередь и множество seen. Очередь будет использоваться для выполнения BFS, а множество seen будет использоваться для предотвращения повторного посещения одного и того же узла. Изначально в очередь и множество должен быть помещен startGene.
Выполняйте BFS. На каждом узле, если node == endGene, return количество шагов, пройденных до этого момента. В противном случае, итеративно заменяйте каждый символ в строке на один из "A", "C", "G", "T" для нахождения соседей. Для каждого соседа, если он еще не был посещен и находится в bank, добавьте его в очередь и в множество seen.
Если BFS завершился и endGene не был найден, Tarefa невыполнима. return -1.
😎
Vacancies for this task
vagas ativas with overlapping task tags are mostradas.