[LeetCode] 269. Alien Dictionary

 Problem : https://leetcode.com/problems/alien-dictionary/

Use topological sort to find order of letters.

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        graph = defaultdict(list)
        indegree = defaultdict(int)
        
        for i in range(1, len(words)):
            for a, b in zip(words[i-1], words[i]):        
                if a != b:
                    graph[a].append(b)
                    indegree[b] += 1
                    break
            else:
                if len(words[i-1]) > len(words[i]):
                    return ''
        
        letters = set([l for w in words for l in w])
        queue = deque([l for l in letters if indegree[l] == 0])
                    
        result = []
        
        while queue:
            for _ in range(len(queue)):
                a = queue.popleft()
                result.append(a)
                
                for b in graph[a]:
                    indegree[b] -= 1
                    if indegree[b] == 0:
                        queue.append(b)
        
        # result is valid if all letters have be resolved.
        return ''.join(result) if len(result) == len(letters) else ""

Edited on 07/22/2021. Update for a shorter solution.

[LeetCode] 871. Minimum Number of Refueling Stops

 Problem: https://leetcode.com/problems/minimum-number-of-refueling-stops/

 Record the amount of gas can get from stations within current maximum distance.

When cannot reach to next station / the target position,  refuel with the maximum amount of gas from the visited gas station to extend the maximum distance can reach and increase refuel count. In the end, check the maximum distance exceeds the target position.

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        maxSoFar = startFuel
        heap = []
        
        i = 0
        refuel = 0
                
        while maxSoFar < target:
            while i < len(stations) and stations[i][0] <= maxSoFar:
                # save gas of station i in heap
                heapq.heappush(heap, -stations[i][1])
                i += 1
            
            if heap:
                # refuel with the maximum amount of gas from visited stations
                maxSoFar += -1 * heapq.heappop(heap)
                refuel += 1
            else:
                break
      
        return refuel if maxSoFar >= target else -1