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

Commitf7d056a

Browse files
committed
433-minimum-genetic-mutation.md AddedA* (A-Star) Search Algorithm solution in Python.
1 parent4c943ca commitf7d056a

File tree

3 files changed

+184
-34
lines changed

3 files changed

+184
-34
lines changed

‎en/1-1000/127-word-ladder.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -51,7 +51,7 @@ The **word transformation sequence** problem can be abstracted into a **graph th
5151
*`Breadth-First Search` emphasizes first-in-first-out, so a**queue** is needed.
5252

5353
##Approach
54-
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.
54+
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.
5555
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.
5656

5757
##Complexity

‎en/1-1000/433-minimum-genetic-mutation.md

Lines changed: 91 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -29,39 +29,38 @@ Note that the starting point is assumed to be valid, so it might not be included
2929
-`startGene.length == endGene.length == bank[i].length == 8`
3030
-`startGene`,`endGene`, and`bank[i]` consist of only the characters`['A', 'C', 'G', 'T']`.
3131

32-
##Intuition
32+
##Intuition 1
3333
We can think of this problem as a shortest path problem on a graph: there are`4^8` vertices (strings`'AAAAAAAA'` to`'TTTTTTTT'`), and there is an edge between two vertices if they differ in one character, and if*both* vertices are in`bank`.
3434

3535
So this issue can be solved by**Breadth-First Search** on a undirected graph.
3636

37-
###Solution 1: Breadth-First Search
3837
![](../../images/binary_tree_BFS_1.gif)
3938

4039
* 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
4140
getting`minimum number` of something of a graph,`Breadth-First Search` would probably help.
4241

4342
*`Breadth-First Search` emphasizes first-in-first-out, so a**queue** is needed.
4443

45-
####Approach
46-
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.
47-
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.
44+
###Approach 1: Breadth-First Search Algorithm
45+
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.
46+
1. So through`Breadth-First Search`, when a word matches`endGene`, the game is over, and we can return the number of**circle** as a result.
4847

49-
####Complexity
48+
###Complexity
5049
>**N** is the length of`bank`.
5150
5251
* Time:`O((8 * 4) * N)`.
5352
* Space:`O(N)`.
5453

55-
###Solution 2: A* (A-Star) Search Algorithm
54+
##Approach 2: A* (A-Star) Search Algorithm
5655

57-
**A-Star Search Algorithm** can be used to improve the performance of**Breadth-First Search Algorithm**.
56+
**A-Star Search Algorithm** can be used togreatlyimprove the performance of**Breadth-First Search Algorithm**.
5857

59-
Please view**A-Star Algorithm** at[752. Open the Lock](./752-open-the-lock.md).
58+
Please viewdetailed**A-Star Algorithm** at[752. Open the Lock](./752-open-the-lock.md).
6059

61-
Bellowis code using_A-Star Search Algorithm_ in Python.
60+
Bellowhas code using_A-Star Search Algorithm_ in Python.
6261

6362
##Python
64-
###Solution 1: Breadth-First Search
63+
###Approach 1: Breadth-First Search (way 1)
6564
```python
6665
classSolution:
6766
defminMutation(self,start_gene:str,end_gene:str,bank: List[str]) ->int:
@@ -70,22 +69,22 @@ class Solution:
7069

7170
self.end_gene= end_gene
7271
self.bank=set(bank)
73-
self.queue= deque([start_gene])
72+
self.queue= deque([start_gene])# difference 1
7473
result=0
7574

7675
whileself.queue:
77-
result+=1
76+
result+=1# difference 2
7877
queue_size=len(self.queue)
7978

80-
for iinrange(queue_size):
79+
for iinrange(queue_size):# difference 3
8180
gene=self.queue.popleft()
8281

8382
ifself.mutate_one(gene):
8483
return result
8584

8685
return-1
8786

88-
defmutate_one(self,gene):
87+
defmutate_one(self,gene):# difference 4
8988
for iinrange(len(gene)):
9089
for charin ['A','C','G','T']:
9190
if gene[i]== char:
@@ -101,9 +100,85 @@ class Solution:
101100
self.bank.remove(mutation)
102101
```
103102

104-
###Solution 2: A* (A-Star) SearchAlgorithm
103+
###Approach 1: Breadth-First Search(way 2 by adding`mutated_count` in queue's item)
105104
```python
105+
classSolution:
106+
defminMutation(self,start_gene:str,end_gene:str,bank: List[str]) ->int:
107+
ifnot end_genein bank:
108+
return-1
109+
110+
self.bank=set(bank)
111+
self.end_gene= end_gene
112+
self.queue= deque([(start_gene,0)])# difference 1
113+
114+
whileself.queue:
115+
gene, mutated_count=self.queue.popleft()# difference 2
116+
117+
ifself.mutate_one(gene, mutated_count):
118+
return mutated_count+1
119+
120+
return-1
121+
122+
defmutate_one(self,gene,mutated_count):# difference 3
123+
for iinrange(len(gene)):
124+
for charin ['A','C','G','T']:
125+
if gene[i]== char:
126+
continue
127+
128+
mutation=f'{gene[:i]}{char}{gene[i+1:]}'
129+
130+
if mutation==self.end_gene:
131+
returnTrue
132+
133+
if mutationinself.bank:
134+
self.queue.append((mutation, mutated_count+1))
135+
self.bank.remove(mutation)
136+
```
137+
138+
###Approach 2: A* (A-Star) Search Algorithm
139+
```python
140+
import heapq
141+
142+
143+
classSolution:
144+
defminMutation(self,start_gene:str,end_gene:str,bank: List[str]) ->int:
145+
ifnot end_genein bank:
146+
return-1
147+
148+
self.end_gene= end_gene
149+
bank=set(bank)
150+
priority_queue= [(self.distance(start_gene), start_gene,0)]# difference 1
151+
152+
while priority_queue:
153+
_, gene, mutated_count= heapq.heappop(priority_queue)# difference 2
154+
155+
for iinrange(len(gene)):
156+
for charin ['A','C','G','T']:
157+
if gene[i]== char:
158+
continue
159+
160+
mutation=f'{gene[:i]}{char}{gene[i+1:]}'
161+
162+
if mutation== end_gene:
163+
return mutated_count+1
164+
165+
if mutationin bank:
166+
heapq.heappush(
167+
priority_queue,
168+
(self.distance(mutation), mutation, mutated_count+1)
169+
)# difference 3
170+
bank.remove(mutation)
171+
172+
return-1
173+
174+
defdistance(self,gene):# difference 4
175+
result=0
176+
177+
for iinrange(8):
178+
if gene[i]!=self.end_gene[i]:
179+
result+=1
106180

181+
return result
107182
```
108183

109184
##JavaScript

‎zh/1-1000/433-minimum-genetic-mutation.md

Lines changed: 92 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -29,39 +29,38 @@ Note that the starting point is assumed to be valid, so it might not be included
2929
-`startGene.length == endGene.length == bank[i].length == 8`
3030
-`startGene`,`endGene`, and`bank[i]` consist of only the characters`['A', 'C', 'G', 'T']`.
3131

32-
##Intuition
32+
##Intuition 1
3333
We can think of this problem as a shortest path problem on a graph: there are`4^8` vertices (strings`'AAAAAAAA'` to`'TTTTTTTT'`), and there is an edge between two vertices if they differ in one character, and if*both* vertices are in`bank`.
3434

3535
So this issue can be solved by**Breadth-First Search** on a undirected graph.
3636

37-
###Solution 1: Breadth-First Search
3837
![](../../images/binary_tree_BFS_1.gif)
3938

4039
* 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
4140
getting`minimum number` of something of a graph,`Breadth-First Search` would probably help.
4241

4342
*`Breadth-First Search` emphasizes first-in-first-out, so a**queue** is needed.
4443

45-
####Approach
46-
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.
47-
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.
44+
###Approach 1: Breadth-First Search Algorithm
45+
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.
46+
1. So through`Breadth-First Search`, when a word matches`endGene`, the game is over, and we can return the number of**circle** as a result.
4847

49-
####Complexity
48+
###Complexity
5049
>**N** is the length of`bank`.
5150
5251
* Time:`O((8 * 4) * N)`.
5352
* Space:`O(N)`.
5453

55-
###Solution 2: A* (A-Star) Algorithm
54+
##Approach 2: A* (A-Star) Search Algorithm
5655

57-
**A-Star Algorithm** can be used to improve the performance of**Breadth-First Search Algorithm**.
56+
**A-StarSearchAlgorithm** can be used to greatly improve the performance of**Breadth-First Search Algorithm**.
5857

59-
Please view**A-Star Algorithm** at[752. Open the Lock](./752-open-the-lock.md).
58+
Please viewdetailed**A-Star Algorithm** at[752. Open the Lock](./752-open-the-lock.md).
6059

61-
Bellowis code using_A-Star Algorithm_ in Python.
60+
Bellowhas code using_A-Star Search Algorithm_ in Python.
6261

6362
##Python
64-
###Solution 1: Breadth-First Search
63+
###Approach 1: Breadth-First Search (way 1)
6564
```python
6665
classSolution:
6766
defminMutation(self,start_gene:str,end_gene:str,bank: List[str]) ->int:
@@ -70,22 +69,22 @@ class Solution:
7069

7170
self.end_gene= end_gene
7271
self.bank=set(bank)
73-
self.queue= deque([start_gene])
72+
self.queue= deque([start_gene])# difference 1
7473
result=0
7574

7675
whileself.queue:
77-
result+=1
76+
result+=1# difference 2
7877
queue_size=len(self.queue)
7978

80-
for iinrange(queue_size):
79+
for iinrange(queue_size):# difference 3
8180
gene=self.queue.popleft()
8281

8382
ifself.mutate_one(gene):
8483
return result
8584

8685
return-1
8786

88-
defmutate_one(self,gene):
87+
defmutate_one(self,gene):# difference 4
8988
for iinrange(len(gene)):
9089
for charin ['A','C','G','T']:
9190
if gene[i]== char:
@@ -101,9 +100,85 @@ class Solution:
101100
self.bank.remove(mutation)
102101
```
103102

104-
###Solution 2: A* (A-Star) Algorithm
103+
###Approach 1: Breadth-First Search (way 2 by adding`mutated_count` in queue's item)
105104
```python
106-
#TODO
105+
classSolution:
106+
defminMutation(self,start_gene:str,end_gene:str,bank: List[str]) ->int:
107+
ifnot end_genein bank:
108+
return-1
109+
110+
self.bank=set(bank)
111+
self.end_gene= end_gene
112+
self.queue= deque([(start_gene,0)])# difference 1
113+
114+
whileself.queue:
115+
gene, mutated_count=self.queue.popleft()# difference 2
116+
117+
ifself.mutate_one(gene, mutated_count):
118+
return mutated_count+1
119+
120+
return-1
121+
122+
defmutate_one(self,gene,mutated_count):# difference 3
123+
for iinrange(len(gene)):
124+
for charin ['A','C','G','T']:
125+
if gene[i]== char:
126+
continue
127+
128+
mutation=f'{gene[:i]}{char}{gene[i+1:]}'
129+
130+
if mutation==self.end_gene:
131+
returnTrue
132+
133+
if mutationinself.bank:
134+
self.queue.append((mutation, mutated_count+1))
135+
self.bank.remove(mutation)
136+
```
137+
138+
###Approach 2: A* (A-Star) Search Algorithm
139+
```python
140+
import heapq
141+
142+
143+
classSolution:
144+
defminMutation(self,start_gene:str,end_gene:str,bank: List[str]) ->int:
145+
ifnot end_genein bank:
146+
return-1
147+
148+
self.end_gene= end_gene
149+
bank=set(bank)
150+
priority_queue= [(self.distance(start_gene), start_gene,0)]# difference 1
151+
152+
while priority_queue:
153+
_, gene, mutated_count= heapq.heappop(priority_queue)# difference 2
154+
155+
for iinrange(len(gene)):
156+
for charin ['A','C','G','T']:
157+
if gene[i]== char:
158+
continue
159+
160+
mutation=f'{gene[:i]}{char}{gene[i+1:]}'
161+
162+
if mutation== end_gene:
163+
return mutated_count+1
164+
165+
if mutationin bank:
166+
heapq.heappush(
167+
priority_queue,
168+
(self.distance(mutation), mutation, mutated_count+1)
169+
)# difference 3
170+
bank.remove(mutation)
171+
172+
return-1
173+
174+
defdistance(self,gene):# difference 4
175+
result=0
176+
177+
for iinrange(8):
178+
if gene[i]!=self.end_gene[i]:
179+
result+=1
180+
181+
return result
107182
```
108183

109184
##JavaScript

0 commit comments

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