# Python Solution using A-star

• All solutions based on BFS are inefficient when the gene sequence is very long. The time complexity of my algorithm is O(k * (n^2)) where n denotes the size of bank and k denotes the length of gene. But the time complexity of the solutions based on BFS are O(k * (4^k)) in general.
My solution treat every gene as a point, and the distance of two genes is defined by the difference between them. Two points is connected Only when the distance is equal to 1. Then the original problem is converted to the shortest path problem which can be solved by A-star.

``````class Solution(object):
def minMutation(self, start, end, bank):
"""
:type start: str
:type end: str
:type bank: List[str]
:rtype: int
"""
if end not in bank:
return -1
if start not in bank:
bank.append(start)
s_index = len(bank) - 1
else:
s_index = bank.index(start)
e_index = bank.index(end)
index_path = []
matrix = self.getMatrix(bank)
d2end = matrix[e_index]
return self.shortestPath(s_index, e_index, matrix, index_path, d2end)

def shortestPath(self, s_i, e_i, matrix, path, d2end):
finded = set()
rest = set()
for i in range(len(d2end)):
wait = []
pre = [-1] * len(d2end)
s2p = [len(d2end) + 1] * len(d2end)
s2p[s_i] = 0
heapq.heappush(wait, (0, s_i))
success = False
while wait:
item = heapq.heappop(wait)
while wait and item[1] in finded:
item = heapq.heappop(wait)
if item[1] in finded:
break
c_i = item[1]
rest.remove(c_i)
if c_i == e_i:
success = True
break;
for point in rest:
if matrix[point][c_i] == 1:
if s2p[point] > s2p[c_i] + 1:
s2p[point] = s2p[c_i] + 1
pre[point] = c_i
heapq.heappush(wait, (s2p[point] + d2end[point], point))
if success:
count = 1
c_i = e_i
while s_i != pre[c_i]:
c_i = pre[c_i]
count = count + 1
return count
else:
return -1

def getMatrix(self, bank):
matrix = [([len(bank[1])] * len(bank)) for i in range(len(bank))]
for i in range(len(bank)):
for j in range(i, len(bank)):
matrix[i][j] = self.distance(bank[i], bank[j])
matrix[j][i] = matrix[i][j]
return matrix

def distance(self, point1, point2):
dif = 0
for i in range(len(point1)):
if point1[i] != point2[i]:
dif = dif + 1
return dif
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.