Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给定基因片段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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理