Python Solution using A-star

  • 0

    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:
                s_index = len(bank) - 1
                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:
                c_i = item[1]
                if c_i == e_i:
                    success = True
                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
                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

Log in to reply

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