[Swift]LeetCode433.最小基因变化|MinimumGeneticMutation

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10334346.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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", "C", "G", "T"中的任意一个。

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

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

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

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

注意:

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

示例 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

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, end, &bank)
 7     }
 8     
 9     func minMutation(_ explored:inout [Bool],_ start:String,_ end:String,_ bank:inout[String]) -> Int
10     {
11         if start == end {return 0}
12         var step:Int = bank.count + 1
13         for i in 0..<bank.count
14         {
15             if diffOne(start, bank[i]) && !explored[i]
16             {
17                 explored[i] = true
18                 var temp:Int = minMutation(&explored, bank[i], end, &bank)
19                 if temp != -1
20                 {
21                     step = min(step, temp)
22                 }
23                 explored[i] = false
24             }            
25         }
26         return step == bank.count + 1 ? -1 : 1 + step
27     }
28     
29     func diffOne(_ s1:String,_ s2:String) -> Bool
30     {
31         var count:Int = 0
32         for i in 0..<s1.count
33         {
34             if s1[i] != s2[i]
35             {
36                 count += 1
37             }
38             if count >= 2
39             {
40                 return false
41             }
42         }
43         return count == 1
44     }
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, _ end: 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 mutationCount
15                 }
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] = c
28                 }
29             }
30             queue = nextQueue
31             mutationCount += 1
32         }
33         return -1
34     }
35 }

12ms

 1 class Solution {
 2       func minMutation(_ start: String, _ end: 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 = 0
10         
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 = 0
21                     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 + 1
26                         }
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 max
41     }
42 }