难度: 中等 | 标签: BFS

1. 题目描述

https://leetcode.cn/problems/minimum-genetic-mutation/
基因序列可以表示为一条由 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’] 组成

通过次数: 21,021 | 提交次数: 39,031

2. 题解

2022-05-07 AC, BFS
更多解法:【宫水三叶】图论搜索 : 「BFS」&「双向 BFS」&「A* 算法」&「建图 + DFS」

  1. <?php
  2. /**
  3.  * Created by PhpStorm
  4.  * User: jtahstu
  5.  * Time: 2022/5/7 0:36
  6.  * Des: 433. 最小基因变化
  7.  *      https://leetcode.cn/problems/minimum-genetic-mutation/
  8.  */
  10. class Solution
  11. {
  12.     public static $list = ['A', 'C', 'G', 'T'];
  14.     /**
  15.      * @param String $start
  16.      * @param String $end
  17.      * @param String[] $bank
  18.      * @return
  19.      */
  20.     function minMutation($start, $end, $bank)
  21.     {
  22.         if ($start == $end) {
  23.             return 0;
  24.         }
  25.         $bank = array_unique($bank);
  26.         if (!in_array($end, $bank)) {
  27.             return -1;
  28.         }
  29.         $res[$start] = 0;
  30.         $wds = [$start];
  31.         while ($wds) {
  32.             $wd = array_shift($wds);
  33.             for ($i = 0; $i < strlen($wd); $i++) {
  34.                 $wd_new = $wd;
  35.                 for ($j = 0; $j < 4; $j++) {
  36.                     if ($wd_new[$i] == self::$list[$j]) {
  37.                         continue;
  38.                     }
  39.                     $wd_new[$i] = self::$list[$j];
  40.                     if (in_array($wd_new, $bank) && !isset($res[$wd_new])) {
  41.                         $res[$wd_new] = $res[$wd] + 1;
  42.                         if ($wd_new == $end) {
  43. //                            print_r($res);
  44.                             return $res[$wd_new];
  45.                         }
  46.                         array_push($wds, $wd_new);
  47.                     }
  48.                 }
  49.             }
  50.         }
  51.         return -1;
  52.     }
  53. }
  55. var_dump((new Solution)->minMutation("AACCGGTT", "AAACGGTA", ["AACCGGTA", "AACCGCTA", "AAACGGTA"]));
  56. var_dump((new Solution)->minMutation("AAAAACCC", "AACCCCCC", ["AAAACCCC", "AAACCCCC", "AACCCCCC"]));
  58. /**
  59.  * 执行用时：12 ms, 在所有 PHP 提交中击败了100.00%的用户
  60.  * 内存消耗：18.4 MB, 在所有 PHP 提交中击败了100.00%的用户
  61.  * 通过测试用例：14 / 14
  62.  */