Leetcode:433. minimal genetic change

433. Minimal genetic change

source ： Power button （LeetCode）

link : https://leetcode.cn/problems/minimum-genetic-mutation/

The gene sequence can be expressed as a sequence composed of 8 A string of characters , Each of these characters is ‘A’、‘C’、‘G’ and ‘T’ One of .

Suppose we need to investigate from the gene sequence start Turn into end Genetic changes that occur . A gene change means that a character in the gene sequence has changed .

• for example ,“AACCGGTT” --> “AACCGGTA” It's a genetic change .

There is another gene bank bank All valid genetic changes were recorded , Only the genes in the gene bank are effective gene sequences .（ The changed gene must be located in the gene pool bank in ）

Here are two gene sequences start and end , And a gene bank bank , Please find out and return what makes start Change to end The minimum number of changes required . If this genetic change cannot be completed , return -1 .

Be careful ： Starting gene sequence start The default is valid , But it doesn't have to be in the gene pool .

Example 1：

 Input ：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
 Output ：1

Example 2：

 Input ：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
 Output ：2

Example 3：

 Input ：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
 Output ：3

Tips ：

• 1 <= n <= 9

solution

• Breadth first traversal BFS： After analysis, we can see that , The title requires that a gene sequence AA Change to another gene sequence BB, We need to meet the following conditions ：
  • Sequence A And Sequence B There is only one character difference between ;
  • Changing characters can only be from ‘A’, ‘C’, ‘G’, ‘T’ To choose from ;
  • The transformed sequence B Must be in the string array bank in
    If start==end, Go straight back to 0; If end be not in bank Medium or bank The length is empty , return -1; Then start traversing start,start Every character of can happen 4 Change , After the change, it needs to be based on bank Check the legitimacy of the changes , If the change equals end, Returns the number of changes , Therefore, it is necessary to synchronize the number of changes saved by a variable . Be careful , Every time it is determined that the change is legal , But it doesn't mean end When , From you to bank Remove the string , Otherwise, it is easy to form a loop , It keeps cycling .

Code implementation

BFS

python Realization

class Solution:
    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
        if start == end:
            return 0
        
        if len(bank) == 0 or end not in bank:
            return -1
        
        q = [(start, 0)]
        while q:
            cur_str, step = q.pop(0)
            for i, x in enumerate(cur_str):
                for y in 'ACGT':
                    if y != x:
                        nxt = cur_str[:i] + y + cur_str[i+1:]
                        if nxt in bank:
                            if nxt == end:
                                return step + 1
                            bank.remove(nxt)
                            q.append((nxt, step+1))
        return -1

c++ Realization

class Solution {
    
public:    
    int minMutation(string start, string end, vector<string>& bank) {
    
        unordered_set<string> cnt;
        unordered_set<string> visited;
        char keys[4] = {
    'A', 'C', 'G', 'T'};        
        for (auto & w : bank) {
    
            cnt.emplace(w);
        }
        if (start == end) {
    
            return 0;
        }
        if (!cnt.count(end)) {
    
            return -1;
        }
        queue<string> qu;
        qu.emplace(start);
        visited.emplace(start);
        int step = 1;
        while (!qu.empty()) {
    
            int sz = qu.size();
            for (int i = 0; i < sz; i++) {
    
                string curr = qu.front();
                qu.pop();
                for (int j = 0; j < 8; j++) {
    
                    for (int k = 0; k < 4; k++) {
    
                        if (keys[k] != curr[j]) {
    
                            string next = curr;
                            next[j] = keys[k];
                            if (!visited.count(next) && cnt.count(next)) {
    
                                if (next == end) {
    
                                    return step;
                                }
                                qu.emplace(next);
                                visited.emplace(next);
                            }
                        }
                    }
                }
            }
            step++;
        }
        return -1;
    }
};

Complexity analysis

• Time complexity ： $O(N\ast M\ast C)$, N Is string start The length of ,C Is a variable number of times , here C=4,M yes bank The length of ;
• Spatial complexity ： $O(N\ast M)$ , N Is string start The length of ,M yes bank The length of , At most in the queue m Elements , The space of each element is O(n), So the space complexity is zero $O(n\times m)$.

Reference resources

• https://leetcode.cn/problems/minimum-genetic-mutation/solution/by-fuxuemingzhu-t1mv/