跳转至

433. 最小基因变化

题目描述

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。

假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

  • 例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。

另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）

给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。

注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。

 

示例 1：

输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
输出：1

示例 2：

输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
输出：2

示例 3：

输入：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
输出：3

 

提示：

  • start.length == 8
  • end.length == 8
  • 0 <= bank.length <= 10
  • bank[i].length == 8
  • start、end 和 bank[i] 仅由字符 ['A', 'C', 'G', 'T'] 组成

解法

方法一：BFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
        s = set(bank)
        q = deque([(start, 0)])
        mp = {'A': 'TCG', 'T': 'ACG', 'C': 'ATG', 'G': 'ATC'}
        while q:
            t, step = q.popleft()
            if t == end:
                return step
            for i, v in enumerate(t):
                for j in mp[v]:
                    next = t[:i] + j + t[i + 1 :]
                    if next in s:
                        q.append((next, step + 1))
                        s.remove(next)
        return -1

 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
class Solution {
    public int minMutation(String start, String end, String[] bank) {
        Set<String> s = new HashSet<>();
        for (String b : bank) {
            s.add(b);
        }
        Map<Character, String> mp = new HashMap<>(4);
        mp.put('A', "TCG");
        mp.put('T', "ACG");
        mp.put('C', "ATG");
        mp.put('G', "ATC");
        Deque<Pair<String, Integer>> q = new LinkedList<>();
        q.offer(new Pair<>(start, 0));
        while (!q.isEmpty()) {
            Pair<String, Integer> p = q.poll();
            String t = p.getKey();
            int step = p.getValue();
            if (end.equals(t)) {
                return step;
            }
            for (int i = 0; i < t.length(); ++i) {
                for (char c : mp.get(t.charAt(i)).toCharArray()) {
                    String next = t.substring(0, i) + c + t.substring(i + 1);
                    if (s.contains(next)) {
                        q.offer(new Pair<>(next, step + 1));
                        s.remove(next);
                    }
                }
            }
        }
        return -1;
    }
}

 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 start, string end, vector<string>& bank) {
        unordered_set<string> s;
        for (auto& b : bank) s.insert(b);
        unordered_map<char, string> mp;
        mp['A'] = "TCG";
        mp['T'] = "ACG";
        mp['C'] = "ATG";
        mp['G'] = "ATC";
        queue<pair<string, int>> q;
        q.push({start, 0});
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            string t = p.first;
            int step = p.second;
            if (t == end) return step;
            for (int i = 0; i < t.size(); ++i) {
                for (char c : mp[t[i]]) {
                    string next = t.substr(0, i) + c + t.substr(i + 1, t.size() - i - 1);
                    if (s.count(next)) {
                        q.push({next, step + 1});
                        s.erase(next);
                    }
                }
            }
        }
        return -1;
    }
};

 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
func minMutation(start string, end string, bank []string) int {
    s := make(map[string]bool)
    for _, b := range bank {
        s[b] = true
    }
    mp := make(map[byte]string)
    mp['A'] = "TCG"
    mp['T'] = "ACG"
    mp['C'] = "ATG"
    mp['G'] = "ATC"
    type pair struct {
        first  string
        second int
    }
    q := []pair{{start, 0}}
    for len(q) > 0 {
        p := q[0]
        q = q[1:]
        t, step := p.first, p.second
        if t == end {
            return step
        }
        for i := 0; i < len(t); i++ {
            for _, c := range mp[t[i]] {
                next := t[:i] + string(c) + t[i+1:]
                if s[next] {
                    q = append(q, pair{next, step + 1})
                    s[next] = false
                }
            }
        }
    }
    return -1
}

 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
function minMutation(start: string, end: string, bank: string[]): number {
    const queue = [start];
    let res = 0;
    while (queue.length !== 0) {
        const n = queue.length;
        for (let i = 0; i < n; i++) {
            const s1 = queue.shift();
            if (s1 === end) {
                return res;
            }

            for (let j = bank.length - 1; j >= 0; j--) {
                const s2 = bank[j];
                let count = 0;
                for (let k = 0; k < 8; k++) {
                    if (s1[k] !== s2[k]) {
                        count++;
                    }
                }
                if (count <= 1) {
                    queue.push(...bank.splice(j, 1));
                }
            }
        }
        res++;
    }
    return -1;
}

 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
use std::collections::VecDeque;
impl Solution {
    pub fn min_mutation(start: String, end: String, mut bank: Vec<String>) -> i32 {
        let mut queue = vec![start].into_iter().collect::<VecDeque<String>>();
        let mut res = 0;
        while !queue.is_empty() {
            let n = queue.len();
            for _ in 0..n {
                let s1 = queue.pop_front().unwrap();
                if s1 == end {
                    return res;
                }

                for i in (0..bank.len()).rev() {
                    let s1 = s1.as_bytes();
                    let s2 = bank[i].as_bytes();
                    let mut count = 0;
                    for j in 0..8 {
                        if s1[j] != s2[j] {
                            count += 1;
                        }
                    }
                    if count <= 1 {
                        queue.push_back(bank.remove(i));
                    }
                }
            }
            res += 1;
        }
        -1
    }
}

方法二：DFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
        def dfs(start, t):
            if start == end:
                nonlocal ans
                ans = min(ans, t)
                return
            for i, x in enumerate(start):
                for y in 'ACGT':
                    if x != y:
                        nxt = start[:i] + y + start[i + 1 :]
                        if nxt in s:
                            s.remove(nxt)
                            dfs(nxt, t + 1)

        s = set(bank)
        ans = inf
        dfs(start, 0)
        return -1 if ans == inf else ans

 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 {
    private int ans;
    private Set<String> s;
    private static final char[] seq = {'A', 'C', 'G', 'T'};

    public int minMutation(String start, String end, String[] bank) {
        s = new HashSet<>();
        for (String b : bank) {
            s.add(b);
        }
        ans = Integer.MAX_VALUE;
        dfs(start, end, 0);
        s.remove(start);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    private void dfs(String start, String end, int t) {
        if (start.equals(end)) {
            ans = Math.min(ans, t);
            return;
        }
        for (int i = 0; i < start.length(); ++i) {
            for (char c : seq) {
                if (start.charAt(i) == c) {
                    continue;
                }
                String nxt = start.substring(0, i) + c + start.substring(i + 1);
                if (s.contains(nxt)) {
                    s.remove(nxt);
                    dfs(nxt, end, t + 1);
                }
            }
        }
    }
}

 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 ans;
    string seq = "ACGT";

    int minMutation(string start, string end, vector<string>& bank) {
        unordered_set<string> s;
        for (auto& b : bank) s.insert(b);
        ans = INT_MAX;
        s.erase(start);
        dfs(start, end, s, 0);
        return ans == INT_MAX ? -1 : ans;
    }

    void dfs(string& start, string& end, unordered_set<string>& s, int t) {
        if (start == end) {
            ans = min(ans, t);
            return;
        }
        for (int i = 0; i < start.size(); ++i) {
            for (char& c : seq) {
                if (start[i] == c) continue;
                string nxt = start.substr(0, i) + c + start.substr(i + 1, start.size() - i - 1);
                if (s.count(nxt)) {
                    s.erase(nxt);
                    dfs(nxt, end, s, t + 1);
                }
            }
        }
    }
};

 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
func minMutation(start string, end string, bank []string) int {
    s := make(map[string]bool)
    for _, b := range bank {
        s[b] = true
    }
    ans := math.MaxInt32
    s[start] = false
    seq := []rune{'A', 'C', 'G', 'T'}
    var dfs func(start string, t int)
    dfs = func(start string, t int) {
        if start == end {
            if ans > t {
                ans = t
            }
            return
        }
        for i, x := range start {
            for _, y := range seq {
                if x == y {
                    continue
                }
                nxt := start[:i] + string(y) + start[i+1:]
                if s[nxt] {
                    s[nxt] = false
                    dfs(nxt, t+1)
                }
            }
        }
    }
    dfs(start, 0)
    if ans == math.MaxInt32 {
        return -1
    }
    return ans
}

评论