Posted on 2022-11-02 17:13
Uriel 閱讀(52)
評論(0) 編輯 收藏 引用 所屬分類:
搜索 、
閑來無事重切Leet Code
給定基因片段start和end，一次變換一位，問幾步可以從start變到end，中間的每一步必須取自bank里面的基因片段，簡單BFS
1 #433
2 #Runtime: 31 ms
3 #Memory Usage: 13.6 MB
4
5 class Solution(object):
6 def nDifference(self, str1, str2):
7 cnt = 0
8 for i in range(len(str1)):
9 if str1[i] != str2[i]:
10 cnt += 1
11 return cnt
12
13
14 def minMutation(self, start, end, bank):
15 """
16 :type start: str
17 :type end: str
18 :type bank: List[str]
19 :rtype: int
20 """
21 if end not in bank:
22 return -1
23 d = [[0] * len(bank)] * len(bank)
24 q = []
25 q.append(start)
26 p = []
27 p.append(0)
28 visit = [0] * len(bank)
29 l = 0
30 r = 1
31 while l < r:
32 if q[l] == end:
33 return p[l]
34 for i in range(len(bank)):
35 if self.nDifference(q[l], bank[i]) == 1 and visit[i] == 0:
36 q.append(bank[i])
37 p.append(p[l] + 1)
38 visit[i] = 1
39 r += 1
40 l += 1
41 return -1