[Swift]LeetCode433. 最小基因变化 | Minimum Genetic Mutation

概述A gene string can be represented by an 8-character long string, with choices from "A", "C", "G", "T". Suppose we need to investigate about a mutation (mutation from "start" to "end"), where ONE mutati

A gene string can be represented by an 8-character long string,with choices from "A", "C", "G", "T".

Suppose we need to investigate about a mutation (mutation from "start" to "end"),where ONE mutation is defined as ONE single character changed in the gene string.

For example, "AACCGGTT" -> "AACCGGTA" is 1 mutation.

Also,there is a given gene "bank",which records all the valID gene mutations. A gene must be in the bank to make it a valID gene string.

Now,given 3 things - start,end,bank,your task is to determine what is the minimum number of mutations needed to mutate from "start" to "end". If there is no such a mutation,return -1.

Note:

Starting point is assumed to be valID,so it might not be included in the bank. If multiple mutations are needed,all mutations during in the sequence must be valID. You may assume start and end string is not the same. 

Example 1:

start: "AACCGGTT"end:   "AACCGGTA"bank: ["AACCGGTA"]return: 1 

Example 2:

start: "AACCGGTT"end:   "AAACGGTA"bank: ["AACCGGTA","AACCGCTA","AAACGGTA"]return: 2 

Example 3:

start: "AAAAACCC"end:   "AACCCCCC"bank: ["AAAACCCC","AAACCCCC","AACCCCCC"]return: 3

一条基因序列由一个带有8个字符的字符串表示，其中每个字符都属于 "A", "T"中的任意一个。

假设我们要调查一个基因序列的变化。一次基因变化意味着这个基因序列中的一个字符发生了变化。

例如，基因序列由"AACCGGTT" 变化至 "AACCGGTA" 即发生了一次基因变化。

与此同时，每一次基因变化的结果，都需要是一个合法的基因串，即该结果属于一个基因库。

现在给定3个参数 — start,bank，分别代表起始基因序列，目标基因序列及基因库，请找出能够使起始基因序列变化为目标基因序列所需的最少变化次数。如果无法实现目标变化，请返回 -1。

注意:

起始基因序列默认是合法的，但是它并不一定会出现在基因库中。 所有的目标基因序列必须是合法的。 假定起始基因序列与目标基因序列是不一样的。

示例 1:

start: "AACCGGTT"end:   "AACCGGTA"bank: ["AACCGGTA"]返回值: 1

示例 2:

start: "AACCGGTT"end:   "AAACGGTA"bank: ["AACCGGTA","AAACGGTA"]返回值: 2

示例 3:

start: "AAAAACCC"end:   "AACCCCCC"bank: ["AAAACCCC","AACCCCCC"]返回值: 3

8ms

 1 class Solution { 2     func minMutation(_ start: String,_ end: String,_ bank: [String]) -> Int { 3         var bank = bank 4         var explored:[Bool] = [Bool](repeating:false,count:bank.count) 5         if bank.isEmpty {return -1} 6         return minMutation(&explored,start,&bank) 7     } 8      9     func minMutation(_ explored:inout [Bool],_ start:String,_ end:String,_ bank:inout[String]) -> Int10     {11         if start == end {return 0}12         var step:Int = bank.count + 113         for i in 0..<bank.count14         {15             if diffOne(start,bank[i]) && !explored[i]16             {17                 explored[i] = true18                 var temp:Int = minMutation(&explored,bank[i],&bank)19                 if temp != -120                 {21                     step = min(step,temp)22                 }23                 explored[i] = false24             }            25         }26         return step == bank.count + 1 ? -1 : 1 + step27     }28     29     func diffOne(_ s1:String,_ s2:String) -> Bool30     {31         var count:Int = 032         for i in 0..<s1.count33         {34             if s1[i] != s2[i]35             {36                 count += 137             }38             if count >= 239             {40                 return false41             }42         }43         return count == 144     }45 }46 47 extension String {        48     //subscript函数可以检索数组中的值49     //直接按照索引方式截取指定索引的字符50     subscript (_ i: Int) -> Character {51         //读取字符52         get {return self[index(startIndex,offsetBy: i)]}53         54     }55 }

10ms

 1 class Solution { 2     func minMutation(_ start: String,_ bank: [String]) -> Int { 3         let geneChoice = [Character("A"),Character("C"),Character("G"),Character("T")] 4         var bankArray = Set(bank.map { Array($0) }) 5         var startArray = Array(start) 6         var endarray = Array(end) 7         var queue = [startArray] 8         var mutationCount = 0 9         while queue.count > 0 {10             var nextQueue = [[Character]]()11             for i in 0 ..< queue.count {12                 var curr = queue[i]13                 if curr == endarray {14                     return mutationCount15                 }16                 for j in 0 ..< 8 {17                     var c = curr[j]18                     for k in 0 ..< geneChoice.count {19                         if c != geneChoice[k] {20                             curr[j] = geneChoice[k]21                             if bankArray.contains(curr) {22                                 nextQueue.append(curr)23                                 bankArray.remove(curr)24                             }25                         }26                     }27                     curr[j] = c28                 }29             }30             queue = nextQueue31             mutationCount += 132         }33         return -134     }35 }

12ms

 1 class Solution { 2       func minMutation(_ start: String,_ bank: [String]) -> Int { 3         if !bank.contains(end){ 4             return -1 5         } 6         if start == end{ 7             return 0 8         } 9         var max :Int = 010         11         var arr = [String]()12         var vists = [String]()13         var temp = [String]()14         arr.append(start)15         while arr.count > 0 {16       17             for j in 0..<arr.count{18                 for k in 0..<bank.count{19                     if vists.contains(bank[k]){continue}20                     var dif :Int = 021                     for  i in 0..<8{22                         let s = arr[j].index(arr[j].startIndex,offsetBy: i)23                         let b = bank[k].index(bank[k].startIndex,offsetBy: i)24                         if arr[j][s] != bank[k][b] {25                             dif = dif + 126                         }27                         if(i == 7  && dif == 1){28                             if bank[k] == end {return max + 1}29                             temp.append(bank[k])30                             vists.append(bank[k])31                         }32                     }33                     34                     35                 }36             }37             if temp.count == 0 {return -1}else{ max = max + 1 }38             arr = temp;temp = [];39         }40         return max41     }42 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode433. 最小基因变化 | Minimum Genetic Mutation全部内容，希望文章能够帮你解决[Swift]LeetCode433. 最小基因变化 | Minimum Genetic Mutation所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。