Skip to main content

269. Alien Dictionary

link

  1. Need to think about the relationship between word(sequence)
  2. Need to convert data(maybe use map for indeg)
  3. Edge case
class Solution:
    def alienOrder(self, words: List[str]) -> str:
        
        n = len(words)

        seen = [0] * 26
        indeg = [0] * 26
        M = defaultdict(set)

        for w in words:
            for s in w:
                seen[ord(s) - 97] = 1

        for i in range(n-1):
            for j in range(len(words[i])):
                # ['abc', 'ab'] should return ''
                if j == len(words[i+1]):
                    return ''
                if words[i][j] == words[i+1][j]:
                    continue
                if ord(words[i+1][j]) - 97 not in M[ord(words[i][j]) - 97]:
                    M[ord(words[i][j]) - 97].add(ord(words[i+1][j]) - 97)
                    indeg[ord(words[i+1][j]) - 97] += 1
                # break need to put this place
                break
        
        dq = deque([i for i in range(26) if seen[i] == 1 and indeg[i] == 0])

        res = ''

        while dq:

            idx = dq.popleft()

            s = chr(idx + 97)

            res = res + s

            for vv in M[idx]:
                indeg[vv] -= 1
                if indeg[vv] == 0:
                    dq.append(vv)

        


        return "" if sum(indeg) != 0 else res