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)): rest.add(i) 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 in finded: item = heapq.heappop(wait) if item in finded: break c_i = item finded.add(c_i) 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)] * 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