LC.P433[最小基因变化]
方法一：BFS(超时)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public int minMutation(String startGene, String endGene, String[] bank) {
Set<String> set = new HashSet<>(List.of(bank));
if (!set.contains(endGene)) return -1;
Deque<String> queue = new ArrayDeque<>();
char[] g = new char[]{'A', 'C', 'G', 'T'};
queue.offer(startGene);
int ans = 0;
while (!queue.isEmpty()) {
int size = queue.size();
++ans;
while (size-- > 0) {
String cur = queue.poll();
char[] s = cur.toCharArray();
for (int i = 0; i < s.length; ++i) {
char char0 = s[i];
for (char c : g) {
if (s[i] == c) continue;
s[i] = c;
String cs = String.valueOf(s);
if (!set.contains(cs)) continue;
if (cs.equals(endGene)) return ans;
queue.offer(cs);
}
s[i] = char0;
}
}
}
return -1;
}
}
|
方法二：BFS+Set去重
通过加入Set，将已经判断过的基因序列直接跳过
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：39.7 MB, 在所有 Java 提交中击败了18.70%的用户
通过测试用例：18 / 18
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
public int minMutation(String startGene, String endGene, String[] bank) {
Set<String> set = new HashSet<>(List.of(bank));
if (!set.contains(endGene)) return -1;
Deque<String> queue = new ArrayDeque<>();
Set<String> visited = new HashSet<>();
char[] g = new char[]{'A', 'C', 'G', 'T'};
queue.offer(startGene);
visited.add(startGene);
int ans = 0;
while (!queue.isEmpty()) {
int size = queue.size();
++ans;
while (size-- > 0) {
String cur = queue.poll();
char[] s = cur.toCharArray();
for (int i = 0; i < s.length; ++i) {
char char0 = s[i];
for (char c : g) {
if (s[i] == c) continue;
s[i] = c;
String cs = String.valueOf(s);
if (!set.contains(cs)) continue;
if (visited.contains(cs)) continue;
if (cs.equals(endGene)) return ans;
queue.offer(cs);
visited.add(cs);
}
s[i] = char0;
}
}
}
return -1;
}
}
|
方法三：双向BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| class Solution {
Set<String> set;
static char[] g = new char[]{'A', 'C', 'G', 'T'};
public int minMutation(String startGene, String endGene, String[] bank) {
set = new HashSet<>(List.of(bank));
if (!set.contains(endGene)) return -1;
set.add(startGene);
Deque<String> queue1 = new ArrayDeque<>(), queue2 = new ArrayDeque<>();
queue1.offer(startGene);
queue2.offer(endGene);
Map<String, Integer> map1 = new HashMap<>(), map2 = new HashMap<>();
map1.put(startGene, 0);
map2.put(endGene, 0);
while (!queue1.isEmpty() && !queue2.isEmpty()) {
int ans;
if (queue1.size() <= queue2.size()) ans = bfs(queue1, map1, map2);
else ans = bfs(queue2, map2, map1);
if (ans != -1) return ans;
}
return -1;
}
private int bfs(Deque<String> queue, Map<String, Integer> map1, Map<String, Integer> map2) {
int size = queue.size();
while (size-- > 0) {
String cur = queue.poll();
char[] s = cur.toCharArray();
int step = map1.get(cur);
for (int i = 0; i < s.length; ++i) {
char char0 = s[i];
for (char c : g) {
if (s[i] == c) continue;
s[i] = c;
String cs = String.valueOf(s);
if (!set.contains(cs) || map1.containsKey(cs)) continue;
if (map2.containsKey(cs)) return map2.get(cs) + step + 1;
queue.offer(cs);
map1.put(cs, step + 1);
}
s[i] = char0;
}
}
return -1;
}
}
|
wechat
