LeetCode 433. 最小基因变化

迷南。 2022-12-23 13:28 126阅读 0赞

### LeetCode 433. 最小基因变化 ###

*  题目：
 *  解题方法：
 *   *  方法1：DFS（深度优先搜索）
     *   *  Java实现

# 题目： #

[LeetCode 433. 最小基因变化][LeetCode 433.]

> 一条基因序列由一个带有8个字符的字符串表示，其中每个字符都属于 “A”, “C”, “G”, “T"中的任意一个。  
> 假设我们要调查一个基因序列的变化。一次基因变化意味着这个基因序列中的一个字符发生了变化。  
> 例如，基因序列由"AACCGGTT” 变化至 “AACCGGTA” 即发生了一次基因变化。  
> 与此同时，每一次基因变化的结果，都需要是一个合法的基因串，即该结果属于一个基因库。  
> 现在给定3个参数 — start, end, bank，分别代表起始基因序列，目标基因序列及基因库，请找出能够使起始基因序列变化为目标基因序列所需的最少变化次数。如果无法实现目标变化，请返回 -1。  
> 注意:  
> 1、起始基因序列默认是合法的，但是它并不一定会出现在基因库中。  
> 2、所有的目标基因序列必须是合法的。  
> 3、假定起始基因序列与目标基因序列是不一样的。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Blbmd4aWFvemhlbjExMTE_size_16_color_FFFFFF_t_70_pic_center]

# 解题方法： #

## 方法1：DFS（深度优先搜索） ##

### Java实现 ###

class Solution {
        // 需要的结果，找出能够使起始基因序列变化为目标基因序列所需的最少变化次数。如果无法实现目标变化，请返回 -1
        // 其实就是暗示说，有些start 变成 end 的 次数不唯一，需要取最小
        int minResult = Integer.MAX_VALUE;
        public int minMutation(String start, String end, String[] bank) {
            char[][] banks = new char[bank.length][start.length()];
            for (int i = 0; i < bank.length; i++) {
                banks[i] = bank[i].toCharArray();
            }
            dfs(start.toCharArray(), end.toCharArray(), banks, 0);
            return minResult == Integer.MAX_VALUE ? -1 : minResult;
        }
    
        public void dfs(char[] start, char[] end, char[][] banks, int change) {
    
            // terminator
            if (Arrays.equals(start, end)) {
                minResult = Math.min(minResult, change);
                return;
            }
    
            for (int i = banks.length - 1; i >= 0 ; i--) {
                // process current level logic
                if (banks[i] == null) { continue; }
                char[] tmp = banks[i];
                int diff = 0;
                for (int j =0; j < start.length; j++) {
                    if (start[j] != tmp[j]) { diff++; }
                }
                if (diff == 1) {
                    banks[i] = null;
                    // drill down
                    dfs(tmp, end, banks, change+1);
                    // reverse current level status
                    banks[i] = tmp;
                }
            }
        }
    }

[LeetCode 433.]: https://leetcode-cn.com/problems/minimum-genetic-mutation/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Blbmd4aWFvemhlbjExMTE_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/a3be536e32f443d0996cb831c72ed10b.png