You signed in with another tab or window.Reload to refresh your session.You signed out in another tab or window.Reload to refresh your session.You switched accounts on another tab or window.Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: en/1-1000/433-minimum-genetic-mutation.md
+23-7Lines changed: 23 additions & 7 deletions
Original file line number
Diff line number
Diff line change
@@ -30,27 +30,38 @@ Note that the starting point is assumed to be valid, so it might not be included
30
30
-`startGene`,`endGene`, and`bank[i]` consist of only the characters`['A', 'C', 'G', 'T']`.
31
31
32
32
##Intuition
33
-
This issuecanbe solved by**Breadth-First Search**.
33
+
Wecanthink 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`.
34
34
35
-
###Breadth-First Search
35
+
So this issue can be solved by**Breadth-First Search** on a undirected graph.
36
+
37
+
###Solution 1: Breadth-First Search
36
38
37
39
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
+
* 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
41
+
getting`minimum number` of something of a graph,`Breadth-First Search` would probably help.
40
42
41
-
*`breadth-first search` emphasizes first-in-first-out, so a**queue** is needed.
43
+
*`Breadth-First Search` emphasizes first-in-first-out, so a**queue** is needed.
42
44
43
-
##Approach
45
+
####Approach
44
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.
45
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.
46
48
47
-
##Complexity
49
+
####Complexity
48
50
>**N** is the length of`bank`.
49
51
50
52
* Time:`O((8 * 4) * N)`.
51
53
* Space:`O(N)`.
52
54
55
+
###Solution 2: A* (A-Star) Algorithm
56
+
57
+
**A-Star Algorithm** can be used to improve the performance of**Breadth-First Search Algorithm**.
58
+
59
+
Please view**A-Star Algorithm** at[752. Open the Lock](./752-open-the-lock.md).
Copy file name to clipboardExpand all lines: zh/1-1000/433-minimum-genetic-mutation.md
+23-7Lines changed: 23 additions & 7 deletions
Original file line number
Diff line number
Diff line change
@@ -30,27 +30,38 @@ Note that the starting point is assumed to be valid, so it might not be included
30
30
-`startGene`,`endGene`, and`bank[i]` consist of only the characters`['A', 'C', 'G', 'T']`.
31
31
32
32
##Intuition
33
-
This issuecanbe solved by**Breadth-First Search**.
33
+
Wecanthink 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`.
34
34
35
-
###Breadth-First Search
35
+
So this issue can be solved by**Breadth-First Search** on a undirected graph.
36
+
37
+
###Solution 1: Breadth-First Search
36
38
37
39
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
+
* 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
41
+
getting`minimum number` of something of a graph,`Breadth-First Search` would probably help.
40
42
41
-
*`breadth-first search` emphasizes first-in-first-out, so a**queue** is needed.
43
+
*`Breadth-First Search` emphasizes first-in-first-out, so a**queue** is needed.
42
44
43
-
##Approach
45
+
####Approach
44
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.
45
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.
46
48
47
-
##Complexity
49
+
####Complexity
48
50
>**N** is the length of`bank`.
49
51
50
52
* Time:`O((8 * 4) * N)`.
51
53
* Space:`O(N)`.
52
54
55
+
###Solution 2: A* (A-Star) Algorithm
56
+
57
+
**A-Star Algorithm** can be used to improve the performance of**Breadth-First Search Algorithm**.
58
+
59
+
Please view**A-Star Algorithm** at[752. Open the Lock](./752-open-the-lock.md).