433. 最小基因变化

题目大意
解题思路
代码

题目大意

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 ‘A’、’C’、’G’ 和 ‘T’ 之一。
假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

例如，”AACCGGTT” —> “AACCGGTA” 就是一次基因变化。

另有一个基因库 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思路

代码
```java public class Solution433 { /**
- “AACCTTGG”
- “AATTCCGG”
- [“AATTCCGG”,”AACCTGGG”,”AACCCCGG”,”AACCTACC”]
- @param args */
  
  public static void main(String[] args) { Solution433 s = new Solution433(); int resp = s.minMutation(“AACCTTGG”, “AATTCCGG”, new String[]{“AATTCCGG”, “AACCTGGG”, “AACCCCGG”, “AACCTACC”}); System.out.println(resp); }
  
  public int minMutation(String start, String end, String[] bank) { //定义一个双向队列 Deque queue = new LinkedList<>(); //是否访问过 Set visited = new HashSet<>(); if (!contains(bank, end) && !start.equals(end)) {
```
 return -1;
```
  } if (start.equals(end)) {
```
 return 0;
```
  } queue.addLast(start); visited.add(start);
  
  int res = 0; while (!queue.isEmpty()) {
```
 int size = queue.size();
 for (int i = 0; i < size; i++) {
     String cur = queue.removeFirst();
     if (cur.equals(end)) {
         return res;
     }
     for (String str : bank) {
         if (canMutate(str, cur) && !visited.contains(str)) {
             queue.addLast(str);
             visited.add(str);
         }
     }
 }
 res++;
```
  } return -1; }
  
  /**
- 判断是否变异的条件当且仅当str1 和 str2 的字符相差1 的时候才可以进行变异 *
- @param str1
- @param str2
- @return */ private boolean canMutate(String str1, String str2) { int count = 0; for (int i = 0; i < str1.length(); i++) {
```
 if (str1.charAt(i) != str2.charAt(i)) {
     count++;
 }
```
  } return count == 1; }
  
  /**
- 返回这个str 是否包含在给定的bank中 *
- @param bank
- @param toFind
- @return */ private boolean contains(String[] bank, String toFind) { for (String b : bank) {
```
 if (b.equals(toFind)) {
     return true;
 }
```
  } return false; }

} ```

来源于力扣每日一题，2022-05-07

433
medium

题目大意

解题思路

代码