433-minimum-genetic-mutation.md Added A* (A-Star) Algorithm description.

gazeldx · gazeldx · commit 83fde217f9d4 · 2025-02-15T19:31:58.000+08:00
diff --git a/en/1-1000/433-minimum-genetic-mutation.md b/en/1-1000/433-minimum-genetic-mutation.md
@@ -30,27 +30,38 @@ Note that the starting point is assumed to be valid, so it might not be included
 - `startGene`, `endGene`, and `bank[i]` consist of only the characters `['A', 'C', 'G', 'T']`.
 
 ## Intuition
-This issue can be solved by **Breadth-First Search**.
+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`.
 
-### Breadth-First Search
+So this issue can be solved by **Breadth-First Search** on a undirected graph.
+
+### Solution 1: Breadth-First Search
 ![](../../images/binary_tree_BFS_1.gif)
 
-* 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
-  getting `shortest` or `least` of something of a graph, `breadth-first search` would probably help.
+* 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
+  getting `minimum number` of something of a graph, `Breadth-First Search` would probably help.
 
-* `breadth-first search` emphasizes first-in-first-out, so a **queue** is needed.
+* `Breadth-First Search` emphasizes first-in-first-out, so a **queue** is needed.
 
-## Approach
+#### Approach
 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.
 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.
 
-## Complexity
+#### Complexity
 > **N** is the length of `bank`.
 
 * Time: `O((8 * 4) * N)`.
 * Space: `O(N)`.
 
+### Solution 2: A* (A-Star) Algorithm
+
+**A-Star Algorithm** can be used to improve the performance of **Breadth-First Search Algorithm**.
+
+Please view **A-Star Algorithm** at [752. Open the Lock](./752-open-the-lock.md).
+
+Bellow is code using _A-Star Algorithm_ in Python.
+
 ## Python
+### Solution 1: Breadth-First Search
 ```python
 class Solution:
     def minMutation(self, start_gene: str, end_gene: str, bank: List[str]) -> int:
@@ -90,6 +101,11 @@ class Solution:
                     self.bank.remove(mutation)
 ```
 
+### Solution 2: A* (A-Star) Algorithm
+```python
+
+```
+
 ## JavaScript
 ```javascript
 // Welcome to create a PR to complete the code of this language, thanks!
diff --git a/zh/1-1000/433-minimum-genetic-mutation.md b/zh/1-1000/433-minimum-genetic-mutation.md
@@ -30,27 +30,38 @@ Note that the starting point is assumed to be valid, so it might not be included
 - `startGene`, `endGene`, and `bank[i]` consist of only the characters `['A', 'C', 'G', 'T']`.
 
 ## Intuition
-This issue can be solved by **Breadth-First Search**.
+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`.
 
-### Breadth-First Search
+So this issue can be solved by **Breadth-First Search** on a undirected graph.
+
+### Solution 1: Breadth-First Search
 ![](../../images/binary_tree_BFS_1.gif)
 
-* 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
-  getting `shortest` or `least` of something of a graph, `breadth-first search` would probably help.
+* 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
+  getting `minimum number` of something of a graph, `Breadth-First Search` would probably help.
 
-* `breadth-first search` emphasizes first-in-first-out, so a **queue** is needed.
+* `Breadth-First Search` emphasizes first-in-first-out, so a **queue** is needed.
 
-## Approach
+#### Approach
 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.
 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.
 
-## Complexity
+#### Complexity
 > **N** is the length of `bank`.
 
 * Time: `O((8 * 4) * N)`.
 * Space: `O(N)`.
 
+### Solution 2: A* (A-Star) Algorithm
+
+**A-Star Algorithm** can be used to improve the performance of **Breadth-First Search Algorithm**.
+
+Please view **A-Star Algorithm** at [752. Open the Lock](./752-open-the-lock.md).
+
+Bellow is code using _A-Star Algorithm_ in Python.
+
 ## Python
+### Solution 1: Breadth-First Search
 ```python
 class Solution:
     def minMutation(self, start_gene: str, end_gene: str, bank: List[str]) -> int:
@@ -90,6 +101,11 @@ class Solution:
                     self.bank.remove(mutation)
 ```
 
+### Solution 2: A* (A-Star) Algorithm
+```python
+# TODO
+```
+
 ## JavaScript
 ```javascript
 // Welcome to create a PR to complete the code of this language, thanks!
