Force deduction solution summary 433- minimum gene change

Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ： Power button

describe ：

The gene sequence can be expressed as a sequence composed of 8 A string of characters , Each of these characters is 'A'、'C'、'G' and 'T' One of .

Suppose we need to investigate from the gene sequence  start Turn into end Genetic changes that occur . A gene change means that a character in the gene sequence has changed .

for example ,"AACCGGTT" --> "AACCGGTA" It's a genetic change .
There is another gene bank bank All valid genetic changes were recorded , Only the genes in the gene bank are effective gene sequences .

Here are two gene sequences start and end , And a gene bank bank , Please find out and return what makes  start Change to end The minimum number of changes required . If this genetic change cannot be completed , return -1 .

Be careful ： Starting gene sequence  start The default is valid , But it doesn't have to be in the gene pool .

Example 1：

Input ：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
Output ：1
Example 2：

Input ：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
Output ：2
Example 3：

Input ：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
Output ：3
 

Tips ：

start.length == 8
end.length == 8
0 <= bank.length <= 10
bank[i].length == 8
start、end and bank[i] Only by characters ['A', 'C', 'G', 'T'] form

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/minimum-genetic-mutation
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  The initial idea is to find the shortest path directly , Just look for those start and end There are changes in position between , But the discovery is not feasible , Because there may be a situation that the unchanged position is changed back in the middle .
*  So in this case , Can only traverse all possibilities .
*  Because the total amount is not much , So we can traverse each time bank, Look for items that can change （ Only one person has been changed ）, Then try to change , And set the array use To record whether... Has been used .
*  If no changeable items are found , Then return to Integer.MAX_VALUE.
*  If the final returned result is less than min, The modified min.

Code ：

public class Solution433 {

    public int minMutation(String start, String end, String[] bank) {
        int min = searchMinRoute(start, end, bank, 0, new int[bank.length]);
        return min == Integer.MAX_VALUE ? -1 : min;
    }

    private int searchMinRoute(String start, String end, String[] bank, int time, int[] use) {
        if (start.equals(end)) {
            return time;
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < bank.length; i++) {
            if (use[i] == 1) {
                continue;
            }
            String current = bank[i];
            int diffNum = getDiffNum(start, current);
            if (diffNum > 1) {
                continue;
            }
            use[i] = 1;
            int i1 = searchMinRoute(current, end, bank, time + 1, use);
            min = Math.min(i1, min);
            use[i] = 0;
        }
        return min;
    }

    private int getDiffNum(String str1, String str2) {
        int num = 0;
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        for (int i = 0; i < chars1.length; i++) {
            if (chars1[i] == chars2[i]) {
                continue;
            }
            num++;
        }
        return num;
    }


}