269. Alien Dictionary (Array, String, Depth-First Search, Breadth-First Search, Graph, Topological Sort)

링크 - https://leetcode.com/problems/alien-dictionary/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Hard

Intuition

우리는 BFS로 이 문제를 풀 수 있다.

1. 먼저 graph를 set을 사용해서 만들어 준다. 각 단어와 그 다음 단어를 비교하고, 거기서 각 글자끼리 비교하면서 다른 부분이 발생을 하면 그 부분에 대해서 graph를 만들어 준다. 그리고 char_depth를 사용해서 각 글자가 거쳤던 횟수를 기록한다.

2. 단어에 다른 부분이 나오지 않았는데 첫번째 단어가 길이가 더 길면 이것은 사전 정의에 어긋나므로 ""를 반환한다.

3. 이제 char_depth의 value가 0인 글자들만 deque에 넣어준다. 값이 0인 글자들의 뜻은 시작 글자라는 뜻이다. 또한 우리는 단어 순서대로 넣었으므로 순서대로 deque에 넣어줘야 한다.

4. 큐가 있을때, popleft를 통해 글자를 뽑아 와 ans에 더해준다. 또한 graph에서 그 글자의 다음 글자들을 set에서 가져온다. 그리고 char_depth에 그 글자들의 값을 1씩 빼주고, 0이 되면 queue에 넣어준다.

5. 답이 char_depth의 길이보다 작으면 우리는 답을 만들 충분한 사전적 정의가 없는 것이므로 ""을 반환한다. 아닐경우, ans를 반환한다.

Code

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        graph = defaultdict(set)
        char_depth = {c:0 for word in words for c in word}

        for word1, word2 in zip(words, words[1:]):
            for c1, c2 in zip(word1, word2):
                if c1 != c2:
                    if c2 not in graph[c1]:
                        graph[c1].add(c2)
                        char_depth[c2] += 1
                    break
            else:
                if len(word1) > len(word2):
                    return ""

        ans = []
        queue = deque([c for c in char_depth if char_depth[c] == 0])
        while queue:
            c = queue.popleft()
            ans.append(c)

            for next_c in graph[c]:
                char_depth[next_c] -= 1
                if char_depth[next_c] == 0:
                    queue.append(next_c)

        if len(ans) < len(char_depth):
            return ""

        return "".join(ans)

Complexity

Time Complexity: O(C) C는 모든 단어들의 길이를 나타낸다.

Space Complexity: O(1) or O(U + min(U^2, N)) N은 총 strings의 개수이고, U는 모든 단어들에 들어있는 unique한 글자들의 개수이다.