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
47
48
49
50
51
52
53
54
55
56
57
58
| class Solution {
private Map<Character, Integer> choices;
public int minMutation(String start, String end, String[] bank) {
if (start.equals(end)) {
return 0;
}
choices = new HashMap<>();
choices.put('A', 1);
choices.put('C', 2);
choices.put('G', 3);
choices.put('T', 4);
Map<Integer, String> geneHashPairs = new HashMap<>();
for (String gene : bank) {
geneHashPairs.putIfAbsent(getHash(gene), gene);
}
if (!geneHashPairs.containsKey(getHash(end))) {
return -1;
}
Deque<Integer> mutations = new ArrayDeque<>();
mutations.offer(getHash(start));
int steps = 0;
while (!mutations.isEmpty()) {
for (int i = mutations.size(); i > 0; i--) {
int currHash = mutations.poll(), offset = (int) (1e8), rollingHash = currHash;
for (int j = 1; j < 9; j++) {
int currDigit = rollingHash / offset;
for (int k = 1; k < 5; k++) {
if (k == currDigit)
continue;
int newHash = currHash - (currDigit * offset) + (k * offset);
if (geneHashPairs.containsKey(newHash)) {
if (geneHashPairs.get(newHash).equals(end)) {
return steps + 1;
} else {
mutations.offer(newHash);
geneHashPairs.remove(newHash);
}
}
}
rollingHash -= (currDigit * offset);
offset /= 10;
}
}
steps += 1;
}
return -1;
}
private int getHash(String gene) {
int hash = 0;
for (char letter : gene.toCharArray()) {
hash += choices.get(letter);
hash *= 10;
}
return hash;
}
}
|
这是很麻烦的解法. 就是计算每一个gene的hash. 从而让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
| class Solution {
public int minMutation(String start, String end, String[] bank) {
Set<String> bankSet = new HashSet<>();
Collections.addAll(bankSet, bank);
if (!bankSet.contains(end))
return -1;
char[] options = new char[] { 'A', 'C', 'G', 'T' };
Deque<String> queue = new ArrayDeque<>();
queue.offer(start);
int steps = 0;
while (!queue.isEmpty()) {
for (int i = queue.size(); i > 0; i--) {
char[] currGene = queue.poll().toCharArray();
for (int k = 0; k < currGene.length; k++) {
char oldOption = currGene[k];
for (char option : options) {
if (option == oldOption)
continue;
currGene[k] = option;
String newGene = new String(currGene);
if (bankSet.contains(newGene)) {
if (newGene.equals(end)) {
return steps + 1;
} else {
queue.offer(newGene);
bankSet.remove(newGene);
}
}
currGene[k] = oldOption;
}
}
}
steps += 1;
}
return -1;
}
}
|
这个做法是最直接的.
时间复杂度和空间复杂度不变.
