This page looks best with JavaScript enabled

Leetcode 433 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 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:

  1. Starting point is assumed to be valid, so it might not be included in the bank.
  2. If multiple mutations are needed, all mutations during in the sequence must be valid.
  3. 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

Accepted 35,543 | Submissions 83,045


題目大意

基因片段長度 8 個鹼基, 一次突變一個鹼基, 突變過程中的基因片段必須要在 bank 中才可以,計算從 start 變成 end 需要突變的次數,不符合規則或是沒辦法的話,return -1 。

思路&過程

  1. 從 start 開始,若 bank 中有與 start 差異為 1,把它從 bank 中移除,紀錄在另一個地方,供再次比對
  2. 紀錄的 ds 為 walked 這個 set()。為了構成迴圈, 一開始就把 start 放入 walked ,每次回圈開始前檢查 end 是否有在 walked 裡面
  3. while loop 何時該停止?
    • 若該次 bank 內沒有東西要移動
    • walked 中已經有 end 了
    • bank 被取光

處理細節

  • 排除 bank = [] 的狀況 (偶爾會忘記 LC 老把戲)
  • 製作判斷鹼基差異的 method
    1. 使用 index 比對兩字串
    2. 若第一次不同: 記下來;第二次直接 return False
  • 用來記錄移動的 bgt_move 選擇 set() , 原因如下:
    1. 方便操作:搬進walked & 從bank移除,所以讓 bgt_move、 bank、 walked 三者使用同種 ds
    2. 選擇 set() 的原因:
      • walked 在 while loop 使用到了in判斷
      • bank 可能很白目的有大量重複
  • 兩層 for loop 讓 bank 在外層,因 bank 每個元素都要處理到,但 walked 不用

my answer

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
        if not bank:
            return -1
        bank, walked = set(bank), {start}
        re = 0
        while end not in walked and bank:
            bgt_move = set() # will be moved
            for b in bank:
                for w in walked:
                    if self.only_one_diff(b, w):
                        bgt_move.add(b)
                        break
            if not bgt_move:
                return -1
            bank -= bgt_move
            walked |= bgt_move
            re += 1
        return re

    @staticmethod
    def only_one_diff(a, b):
        fond_diff = False
        for i in range(len(a)):
            if a[i] != b[i]:
                if fond_diff:
                    return False
                fond_diff = True
        return True

testcase

s = "AACCTTGG"
e = "AATTCCGG"
b = []
t = Solution().minMutation(s, e, b)
print(t)

s = "AACCGGTT"
e = "AACCGGTA"
b = ["AACCGGTA"]
t = Solution().minMutation(s, e, b)
print(t)

s = "AACCGGTT"
e = "AAACGGTA"
b = ["AACCGGTA", "AACCGCTA", "AAACGGTA"]
t = Solution().minMutation(s, e, b)
print(t)

s = "AAAAACCC"
e = "AACCCCCC"
b = ["AAAACCCC", "AAACCCCC", "AACCCCCC"]
t = Solution().minMutation(s, e, b)
print(t)

s = "AACCTTGG"
e = "AATTCCGG"
b = ["AATTCCGG", "AACCTGGG", "AACCCCGG", "AACCTACC"]
t = Solution().minMutation(s, e, b)
print(t)