LeetCode 433. 最小基因变化（广度优先搜索）-白红宇

LeetCode 433. 最小基因变化（广度优先搜索）

阅读量：2006 次

发布时间：2019-04-28

本文共 1722 字，大约阅读时间需要 5 分钟。

1. 题目

一条基因序列由一个带有8个字符的字符串表示，其中每个字符都属于 “A”, “C”, “G”, "T"中的任意一个。

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

例如，基因序列由"AACCGGTT" 变化至 “AACCGGTA” 即发生了一次基因变化。

与此同时，每一次基因变化的结果，都需要是一个合法的基因串，即该结果属于一个基因库。

现在给定3个参数 — start, end, bank，分别代表起始基因序列，目标基因序列及基因库，请找出能够使起始基因序列变化为目标基因序列所需的最少变化次数。

如果无法实现目标变化，请返回 -1。

注意:起始基因序列默认是合法的，但是它并不一定会出现在基因库中。所有的目标基因序列必须是合法的。假定起始基因序列与目标基因序列是不一样的。示例 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-genetic-mutation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. BFS解题

模板题，用队列实现，每个单词的字符变成4种可能

bank 字符串插入哈希set中，找到了就删除（访问过了）

class Solution {
   public:    int minMutation(string start, string end, vector
   
    & bank) {
       	if(start.size()!=end.size())    		return -1;    	unordered_set
    
      s;    	for(string& b : bank)    		s.insert(b);//同时兼做未访问的集合    	if(!s.count(end)) return -1;    	queue
     
       q;    	string cur, temp;    	int step = 0, n, i, j;    	char ch[4] = {
   'A','G','C','T'};    	q.push(start);        if(s.count(start))            s.erase(start);    	while(!q.empty())    	{
       		n = q.size();    		while(n--)    		{
       			cur = q.front();    			if(cur == end)    				return step;	    		q.pop();	    		for(i = 0; i < cur.size(); ++i)	    		{
   	    			for(j = 0; j < 4; ++j)	    			{
   	    				temp = cur;	    				temp[i] = ch[j];	    				if(s.count(temp))//未访问的	    				{
   	    					q.push(temp);	    					s.erase(temp);	    				}	    			}	    		}    		}    		step++;    	}    	return -1;    }};