目录
最⼩基因变化（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
基因序列可以表⽰为⼀条由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'] 组成
讲解算法原理
解法：
算法思路：
如果将「每次字符串的变换」抽象成图中的「两个顶点和⼀条边」的话，问题就变成了「边权为1的最短路问题」。
因此，从起始的字符串开始，来⼀次 bfs 即可。
编写代码
c++算法代码：
class Solution
{
public:
int minMutation(string startGene, string endGene, vector<string>& bank)
{
unordered_set<string> vis; // ⽤来标记已经搜索过的状态
unordered_set<string> hash(bank.begin(), bank.end()); // 存储基因库⾥⾯的字符串
string change = "ACGT";
if(startGene == endGene) return 0;
if(!hash.count(endGene)) return -1;
queue<string> q;
q.push(startGene);
vis.insert(startGene);
int ret = 0;
while(q.size())
{
ret++;
int sz = q.size();
while(sz--)
{
string t = q.front();
q.pop();
for(int i = 0; i < 8; i++)
{
string tmp = t; // 细节问题
for(int j = 0; j < 4; j++)
{
tmp[i] = change[j];
if(hash.count(tmp) && !vis.count(tmp))
{
if(tmp == endGene) return ret;
q.push(tmp);
vis.insert(tmp);
}
}
}
}
}
return -1;
}
};java算法代码：
class Solution
{
public int minMutation(String startGene, String endGene, String[] bank)
{
Set<String> vis = new HashSet<>(); // ⽤来标记已经搜索过的状态
Set<String> hash = new HashSet<>(); // ⽤来统计基因库⾥⾯的字符串
for(String s : bank) hash.add(s);
char[] change = {'A', 'C', 'G', 'T'};
if(startGene.equals(endGene)) return 0;
if(!hash.contains(endGene)) return -1;
Queue<String> q = new LinkedList<>();
q.add(startGene);
vis.add(startGene);
int step = 0;
while(!q.isEmpty())
{
step++;
int sz = q.size();
while(sz-- != 0)
{
String t = q.poll();
for(int i = 0; i < 8; i++)
{
char[] tmp = t.toCharArray();
for(int j = 0; j < 4; j++)
{
tmp[i] = change[j];
String next = new String(tmp);
if(hash.contains(next) && !vis.contains(next))
{
if(next.equals(endGene)) return step;
q.add(next);
vis.add(next);
}
}
}
}
}
return -1;
}
}单词接⻰（hard）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
字典 wordList 中从单词 beginWord 和 endWord 的转换序列是⼀个按下述规格形成的序列 beginWord -> s(1) -> s(2) -> ... -> s(k) ：
• 每⼀对相邻的单词只差⼀个字⺟。
• 对于 1 <= i <= k 时，每个 s(i) 都在 wordList 中。注意， beginWord 不需要
在 wordList 中。
• s(k) == endWord
给你两个单词 beginWord 和 endWord 和⼀个字典 wordList ，返回从 beginWord 到endWord 的最短转换序列中的单词数⽬。如果不存在这样的转换序列，返回 0 。
⽰例1：
输⼊：beginWord="hit",endWord="cog",wordList=["hot","dot","dog","lot","log","cog"]输出：5
解释：⼀个最短转换序列是"hit"->"hot"->"dot"->"dog"->"cog",返回它的⻓度5。⽰例2：
输⼊：beginWord="hit",endWord="cog",wordList=["hot","dot","dog","lot","log"]输出：0
解释：endWord"cog"不在字典中，所以⽆法进⾏转换。
提⽰：
◦ 1 <= beginWord.length <= 10
◦ endWord.length == beginWord.length
◦ 1 <= wordList.length <= 5000
◦ wordList[i].length == beginWord.length
◦ beginWord 、 endWord 和 wordList[i] 由⼩写英⽂字⺟组成
◦ beginWord != endWord
◦ wordList 中的所有字符串互不相同
讲解算法原理
解法：
算法思路：
跟上题⼀样~
编写代码
c++算法代码：
class Solution
{
public:
int ladderLength(string beginWord, string endWord, vector<string>&
wordList)
{
unordered_set<string> hash(wordList.begin(), wordList.end());
unordered_set<string> vis; // 标记已经搜索过的单词
if(!hash.count(endWord)) return 0;
queue<string> q;
q.push(beginWord);
vis.insert(beginWord);
int ret = 1;
while(q.size())
{
ret++;
int sz = q.size();
while(sz--)
{
string t = q.front();
q.pop();
for(int i = 0; i < t.size(); i++)
{
string tmp = t;
for(char ch = 'a'; ch <= 'z'; ch++)
{
tmp[i] = ch;
if( hash.count(tmp) && !vis.count(tmp))
{
if(tmp == endWord) return ret;
q.push(tmp);
vis.insert(tmp);
}
}
}
}
}
return 0;
}
};java算法代码：
class Solution
{
public int ladderLength(String beginWord, String endWord, List<String>
wordList)
{
Set<String> hash = new HashSet<>();
for(String s : wordList) hash.add(s);
Set<String> vis = new HashSet<>(); // 标记已经搜索过的单词
if(!hash.contains(endWord)) return 0;
Queue<String> q = new LinkedList<>();
q.add(beginWord);
vis.add(beginWord);
int ret = 1;
while(!q.isEmpty())
{
ret++;
int sz = q.size();
while(sz-- != 0)
{
String t = q.poll();
for(int i = 0; i < t.length(); i++)
{
char[] tmp = t.toCharArray();
for(char ch = 'a'; ch <= 'z'; ch++)
{
tmp[i] = ch;
String next = new String(tmp);
if(hash.contains(next) && !vis.contains(next))
{
if(next.equals(endWord)) return ret;
q.add(next);
vis.add(next);
}
}
}
}
}
return 0;
}
}