05 August 2008
给两个gene字符串，每个字符串八个字符，再给一个字典，检查从一个gene变成另外一个gene最小的步数，中间过程在字典里面，类似单词接龙word ladder
BFS，将start字符串每次变化一个字符形成一个新的字符串，当变换后的新字符串在基因库中不存在就不继续处理，同时利用map记录变化后的新串，避免重复计算，直到变化后的某个字符串与end相同。
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
class Solution {
public int minMutation(String start, String end, String[] bank) {
List<String> list = Arrays.asList(bank); //存储合法的基因序列
Deque<String> deque = new ArrayDeque<>(); //广度优先队列，存储start字符串每个下标字符变化时的新字符串
//使用map的原因是假设原基因序列为AGCT....，变化第一个字符后为CGCT....,GGCT....，TGCT....，并且将这三个基因序列加入队列
//下次取出队头元素CGCT....时，变化第一个字符后为GGCT....,AGCT....,TGCT....，这时判断出map中已经存在AGCT....,GGCT....,
//TGCT....,就避免了重复计算，也可同时得到从一个字符串变到另一个字符串的最少变化次数
Map<String, Integer> map = new HashMap<>(); //记录start字符串每个下标字符变化时的新字符串以及经过多少次变化可以得到西新
String[] gene = {"A", "T", "C", "G"};
deque.add(start);
map.put(start, 0);
while (!deque.isEmpty()) {
String s = deque.poll(); //取队头元素
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 4; j++) {
if (String.valueOf(s.charAt(i)).equals(gene[j])) continue; //如果s下标为i的字符与gene下标为j的字符相同则进行下一次循环
String ns = s.substring(0, i) + gene[j] + s.substring(i + 1, s.length()); //变化一个位置的字符后形成新的字符串
// System.out.println(ns);
if (!list.contains(ns)) continue; //如果合法基因库中不包含变化后的新字符串则进入下一次循环
if (!map.containsKey(ns)) {
map.put(ns, map.get(s) + 1);
deque.add(ns);
if (ns.equals(end)) return map.get(ns);
}
}
}
}
return -1;
}
}
改造一下用Set 时间复杂度 O(N * M * K) :
N is length of start string
M is number of letters in gene
K is number of strings in bank
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
class Solution {
public int minMutation(String start, String end, String[] bank) {
int steps = 0;
if (start.equals(end)) {
return steps;
}
HashSet<String> bankSet = new HashSet<>(Arrays.asList(bank));
HashSet<String> visited = new HashSet<>();
Deque<String> queue = new ArrayDeque<>(); //广度优先队列，存储start字符串每个下标字符变化时的新字符串
char[] gene = {'A', 'T', 'C', 'G'};
queue.add(start);
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
String curr = queue.poll();
if (curr.equals(end)) {
return steps;
}
char[] currArray = curr.toCharArray();
for (int i = 0; i < currArray.length; i++) {
char old = currArray[i];
for (char c : gene) {
currArray[i] = c;
String next = new String(currArray);
if (!visited.contains(next) && bankSet.contains(next)) {
visited.add(next);
queue.offer(next);
}
}
currArray[i] = old;
}
}
steps++;
}
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 {
public int minMutation(String start, String end, String[] bank) {
// 定义三个集合，分别是合法基因集合，起始基因集合，目标基因集合
Set<String> dict = new HashSet<>(), st = new HashSet<>(), ed = new HashSet<>();
for (String s : bank) dict.add(s);
// 基因库中不包含目标，则无法转换
if (!dict.contains(end)) return -1;
st.add(start);
ed.add(end);
// 宽搜
return bfs(st, ed, dict, 0);
}
// 宽搜
private int bfs(Set<String> st, Set<String> ed, Set<String> dict, int len) {
// 起始集合为空，那么就无法到达目标
if (st.size() == 0) return -1;
// 优先从数量少的一端开始搜索，减少搜索量
if (st.size() > ed.size()) return bfs(ed, st, dict, len);
Set<String> next = new HashSet<>();
char[] mode = {'A', 'C', 'G', 'T'};
// 枚举起始集合可以一步转换的所有基因序列
for (String s : st) {
StringBuilder temp = new StringBuilder(s);
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 4; j++) {
// 不包含相同的字符
if (s.charAt(i) == mode[j]) continue;
temp.setCharAt(i, mode[j]);
String cur = temp.toString();
// 终点集合中包含了当前字符，那么直接返回步数
if (ed.contains(cur)) return len + 1;
// 如果是合法序列，则加入下一个搜索集合中
if (dict.contains(cur)) {
next.add(cur);
}
temp.setCharAt(i, s.charAt(i));
}
}
}
// 搜索下一层
return bfs(next, ed, dict, len + 1);
}
}
DFS
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
class Solution {
/*
https://leetcode.com/problems/minimum-genetic-mutation/discuss/91484/Java-Solution-using-BFS
*/
public int minMutation(String start, String end, String[] bank) {
//BFS或者DFS，这里用DFS
recurse(start, end, bank, 0, new HashSet<String>());
return count == Integer.MAX_VALUE ? -1 : count;
}
int count = Integer.MAX_VALUE;
private void recurse(String start, String end, String[] bank, int soFar, Set<String> visited) {
if (start.intern() == end.intern()) {
count = Math.min(count, soFar);
}
for (String e : bank) {
int diff = 0;
for (int i = 0; i < e.length(); i++) {
if (start.charAt(i) != e.charAt(i)) {
diff++;
if (diff > 1) {
break;
}
}
}
if (diff == 1 && !visited.contains(e)) {
visited.add(e);
recurse(e, end, bank, soFar+1, visited);
visited.remove(e);
}
}
}
}