Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit34715c6

Browse files
committed
433-minimum-genetic-mutation.md Added Python solution.
1 parent8c0c792 commit34715c6

File tree

3 files changed

+255
-0
lines changed

3 files changed

+255
-0
lines changed

‎README.md

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -119,4 +119,7 @@ You can skip the more difficult problems and do them later.
119119
-[787. Cheapest Flights Within K Stops](en/1-1000/787-cheapest-flights-within-k-stops.md) was solved in_Python_.
120120
-[1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance](en/1001-2000/1334-find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance.md) was solved in_Python_.
121121

122+
#Others
123+
-[433. Minimum Genetic Mutation](en/1-1000/433-minimum-genetic-mutation.md) was solved in_Python_.
124+
122125
More LeetCode problems will be added soon.
Lines changed: 126 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,126 @@
1+
#433. Minimum Genetic Mutation - Best Practices of LeetCode Solutions
2+
LeetCode link:[433. Minimum Genetic Mutation](https://leetcode.com/problems/minimum-genetic-mutation), difficulty:**Medium**.
3+
4+
##LeetCode description of "433. Minimum Genetic Mutation"
5+
A gene string can be represented by an 8-character long string, with choices from`A`,`C`,`G`, and`T`.
6+
7+
Suppose we need to investigate a mutation from a gene string`startGene` to a gene string`endGene` where one mutation is defined as one single character changed in the gene string.
8+
9+
* For example,`"AACCGGTT" --> "AACCGGTA"` is one mutation.
10+
11+
There is also a gene bank`bank` that records all the valid gene mutations. A gene must be in`bank` to make it a valid gene string.
12+
13+
Given the two gene strings`startGene` and`endGene` and the gene bank`bank`, return_the minimum number of mutations needed to mutate from`startGene` to`endGene`_. If there is no such a mutation, return`-1`.
14+
15+
Note that the starting point is assumed to be valid, so it might not be included in the bank.
16+
17+
###[Example 1]
18+
**Input**:`startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]`
19+
20+
**Output**:`1`
21+
22+
###[Example 2]
23+
**Input**:`startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]`
24+
25+
**Output**:`2`
26+
27+
###[Constraints]
28+
-`0 <= bank.length <= 10`
29+
-`startGene.length == endGene.length == bank[i].length == 8`
30+
-`startGene`,`endGene`, and`bank[i]` consist of only the characters`['A', 'C', 'G', 'T']`.
31+
32+
##Intuition
33+
This issue can be solved by**Breadth-First Search**.
34+
35+
###Breadth-First Search
36+
![](../../images/binary_tree_BFS_1.gif)
37+
38+
* As shown in the figure above,**breadth-first search** can be thought of as visiting vertices in rounds and rounds. Actually, whenever you see a question is about
39+
getting`shortest` or`least` of something of a graph,`breadth-first search` would probably help.
40+
41+
*`breadth-first search` emphasizes first-in-first-out, so a**queue** is needed.
42+
43+
##Approach
44+
1.`Breadth-First Search` a graph means traversing**from near to far**, from`circle 1` to`circle N`. Each`circle` is a round of iteration, but we can simplify it by using just 1 round.
45+
1. So through`Breadth-First Search`, when a word matches`endWord`, the game is over, and we can return the number of**circle** as a result.
46+
47+
##Complexity
48+
>**N** is the length of`bank`.
49+
50+
* Time:`O((8 * 4) * N)`.
51+
* Space:`O(N)`.
52+
53+
##Python
54+
```python
55+
classSolution:
56+
defminMutation(self,start_gene:str,end_gene:str,bank: List[str]) ->int:
57+
ifnot end_genein bank:
58+
return-1
59+
60+
self.end_gene= end_gene
61+
self.bank=set(bank)
62+
self.queue= deque([start_gene])
63+
result=0
64+
65+
whileself.queue:
66+
result+=1
67+
queue_size=len(self.queue)
68+
69+
for iinrange(queue_size):
70+
gene=self.queue.popleft()
71+
72+
ifself.mutate_one(gene):
73+
return result
74+
75+
return-1
76+
77+
defmutate_one(self,gene):
78+
for iinrange(len(gene)):
79+
for charin ['A','C','G','T']:
80+
if gene[i]== char:
81+
continue
82+
83+
mutation=f'{gene[:i]}{char}{gene[i+1:]}'
84+
85+
if mutation==self.end_gene:
86+
returnTrue
87+
88+
if mutationinself.bank:
89+
self.queue.append(mutation)
90+
self.bank.remove(mutation)
91+
```
92+
93+
##JavaScript
94+
```javascript
95+
// Welcome to create a PR to complete the code of this language, thanks!
96+
```
97+
98+
##Java
99+
```java
100+
// Welcome to create a PR to complete the code of this language, thanks!
101+
```
102+
103+
##C++
104+
```cpp
105+
// Welcome to create a PR to complete the code of this language, thanks!
106+
```
107+
108+
##C#
109+
```c#
110+
// Welcome to create a PR to complete the code of this language, thanks!
111+
```
112+
113+
##Go
114+
```go
115+
// Welcome to create a PR to complete the code of this language, thanks!
116+
```
117+
118+
##Ruby
119+
```ruby
120+
# Welcome to create a PR to complete the code of this language, thanks!
121+
```
122+
123+
##C, Kotlin, Swift, Rust or other languages
124+
```
125+
// Welcome to create a PR to complete the code of this language, thanks!
126+
```
Lines changed: 126 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,126 @@
1+
#433. Minimum Genetic Mutation - Best Practices of LeetCode Solutions
2+
LeetCode link:[433. Minimum Genetic Mutation](https://leetcode.com/problems/minimum-genetic-mutation), difficulty:**Medium**.
3+
4+
##LeetCode description of "433. Minimum Genetic Mutation"
5+
A gene string can be represented by an 8-character long string, with choices from`A`,`C`,`G`, and`T`.
6+
7+
Suppose we need to investigate a mutation from a gene string`startGene` to a gene string`endGene` where one mutation is defined as one single character changed in the gene string.
8+
9+
* For example,`"AACCGGTT" --> "AACCGGTA"` is one mutation.
10+
11+
There is also a gene bank`bank` that records all the valid gene mutations. A gene must be in`bank` to make it a valid gene string.
12+
13+
Given the two gene strings`startGene` and`endGene` and the gene bank`bank`, return_the minimum number of mutations needed to mutate from`startGene` to`endGene`_. If there is no such a mutation, return`-1`.
14+
15+
Note that the starting point is assumed to be valid, so it might not be included in the bank.
16+
17+
###[Example 1]
18+
**Input**:`startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]`
19+
20+
**Output**:`1`
21+
22+
###[Example 2]
23+
**Input**:`startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]`
24+
25+
**Output**:`2`
26+
27+
###[Constraints]
28+
-`0 <= bank.length <= 10`
29+
-`startGene.length == endGene.length == bank[i].length == 8`
30+
-`startGene`,`endGene`, and`bank[i]` consist of only the characters`['A', 'C', 'G', 'T']`.
31+
32+
##Intuition
33+
This issue can be solved by**Breadth-First Search**.
34+
35+
###Breadth-First Search
36+
![](../../images/binary_tree_BFS_1.gif)
37+
38+
* As shown in the figure above,**breadth-first search** can be thought of as visiting vertices in rounds and rounds. Actually, whenever you see a question is about
39+
getting`shortest` or`least` of something of a graph,`breadth-first search` would probably help.
40+
41+
*`breadth-first search` emphasizes first-in-first-out, so a**queue** is needed.
42+
43+
##Approach
44+
1.`Breadth-First Search` a graph means traversing**from near to far**, from`circle 1` to`circle N`. Each`circle` is a round of iteration, but we can simplify it by using just 1 round.
45+
1. So through`Breadth-First Search`, when a word matches`endWord`, the game is over, and we can return the number of**circle** as a result.
46+
47+
##Complexity
48+
>**N** is the length of`bank`.
49+
50+
* Time:`O((8 * 4) * N)`.
51+
* Space:`O(N)`.
52+
53+
##Python
54+
```python
55+
classSolution:
56+
defminMutation(self,start_gene:str,end_gene:str,bank: List[str]) ->int:
57+
ifnot end_genein bank:
58+
return-1
59+
60+
self.end_gene= end_gene
61+
self.bank=set(bank)
62+
self.queue= deque([start_gene])
63+
result=0
64+
65+
whileself.queue:
66+
result+=1
67+
queue_size=len(self.queue)
68+
69+
for iinrange(queue_size):
70+
gene=self.queue.popleft()
71+
72+
ifself.mutate_one(gene):
73+
return result
74+
75+
return-1
76+
77+
defmutate_one(self,gene):
78+
for iinrange(len(gene)):
79+
for charin ['A','C','G','T']:
80+
if gene[i]== char:
81+
continue
82+
83+
mutation=f'{gene[:i]}{char}{gene[i+1:]}'
84+
85+
if mutation==self.end_gene:
86+
returnTrue
87+
88+
if mutationinself.bank:
89+
self.queue.append(mutation)
90+
self.bank.remove(mutation)
91+
```
92+
93+
##JavaScript
94+
```javascript
95+
// Welcome to create a PR to complete the code of this language, thanks!
96+
```
97+
98+
##Java
99+
```java
100+
// Welcome to create a PR to complete the code of this language, thanks!
101+
```
102+
103+
##C++
104+
```cpp
105+
// Welcome to create a PR to complete the code of this language, thanks!
106+
```
107+
108+
##C#
109+
```c#
110+
// Welcome to create a PR to complete the code of this language, thanks!
111+
```
112+
113+
##Go
114+
```go
115+
// Welcome to create a PR to complete the code of this language, thanks!
116+
```
117+
118+
##Ruby
119+
```ruby
120+
# Welcome to create a PR to complete the code of this language, thanks!
121+
```
122+
123+
##C, Kotlin, Swift, Rust or other languages
124+
```
125+
// Welcome to create a PR to complete the code of this language, thanks!
126+
```

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp