Python Solution using A-star


  • 0
    C

    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[1] in finded:
                    item = heapq.heappop(wait)
                if item[1] in finded:
                    break
                c_i = item[1]
                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[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.