Skip to content

Commit f7d056a

Browse files
gazeldxgazeldx
committed
433-minimum-genetic-mutation.md Added A* (A-Star) Search Algorithm solution in Python.
1 parent 4c943ca commit f7d056a

File tree

3 files changed

+184
-34
lines changed

3 files changed

+184
-34
lines changed

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

+1-1
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

+91-16
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 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 view detailed **A-Star Algorithm** at [752. Open the Lock](./752-open-the-lock.md).
6059

61-
Bellow is code using _A-Star Search Algorithm_ in Python.
60+
Bellow has 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
class Solution:
6766
def minMutation(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
while self.queue:
77-
result += 1
76+
result += 1 # difference 2
7877
queue_size = len(self.queue)
7978

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

8382
if self.mutate_one(gene):
8483
return result
8584

8685
return -1
8786

88-
def mutate_one(self, gene):
87+
def mutate_one(self, gene): # difference 4
8988
for i in range(len(gene)):
9089
for char in ['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) Search Algorithm
103+
### Approach 1: Breadth-First Search (way 2 by adding `mutated_count` in queue's item)
105104
```python
105+
class Solution:
106+
def minMutation(self, start_gene: str, end_gene: str, bank: List[str]) -> int:
107+
if not end_gene in 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+
while self.queue:
115+
gene, mutated_count = self.queue.popleft() # difference 2
116+
117+
if self.mutate_one(gene, mutated_count):
118+
return mutated_count + 1
119+
120+
return -1
121+
122+
def mutate_one(self, gene, mutated_count): # difference 3
123+
for i in range(len(gene)):
124+
for char in ['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+
return True
132+
133+
if mutation in self.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+
class Solution:
144+
def minMutation(self, start_gene: str, end_gene: str, bank: List[str]) -> int:
145+
if not end_gene in 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 i in range(len(gene)):
156+
for char in ['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 mutation in 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+
def distance(self, gene): # difference 4
175+
result = 0
176+
177+
for i in range(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

+92-17
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-Star Search Algorithm** 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 view detailed **A-Star Algorithm** at [752. Open the Lock](./752-open-the-lock.md).
6059

61-
Bellow is code using _A-Star Algorithm_ in Python.
60+
Bellow has 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
class Solution:
6766
def minMutation(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
while self.queue:
77-
result += 1
76+
result += 1 # difference 2
7877
queue_size = len(self.queue)
7978

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

8382
if self.mutate_one(gene):
8483
return result
8584

8685
return -1
8786

88-
def mutate_one(self, gene):
87+
def mutate_one(self, gene): # difference 4
8988
for i in range(len(gene)):
9089
for char in ['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+
class Solution:
106+
def minMutation(self, start_gene: str, end_gene: str, bank: List[str]) -> int:
107+
if not end_gene in 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+
while self.queue:
115+
gene, mutated_count = self.queue.popleft() # difference 2
116+
117+
if self.mutate_one(gene, mutated_count):
118+
return mutated_count + 1
119+
120+
return -1
121+
122+
def mutate_one(self, gene, mutated_count): # difference 3
123+
for i in range(len(gene)):
124+
for char in ['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+
return True
132+
133+
if mutation in self.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+
class Solution:
144+
def minMutation(self, start_gene: str, end_gene: str, bank: List[str]) -> int:
145+
if not end_gene in 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 i in range(len(gene)):
156+
for char in ['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 mutation in 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+
def distance(self, gene): # difference 4
175+
result = 0
176+
177+
for i in range(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)